We study oxidative coupling of methane (OCM) on alkaline earth metal oxides (AEMOs) doped with either a transition metal (TM) or an alkaline earth metal (AEM) different from that of the host oxide. We assess whether doping can lead to new materials that are better than the pure oxides or deviate from the limitations of the scaling relations. Density functional theory (DFT) calculations show that doped AEMO surfaces follow similar linear scaling relations as observed on pure AEMO; however, doped surfaces bind the adsorbates, hydrogen, and methyl more strongly. Both TM- and AEM-doped AEMOs show that methane activation mostly occurs through a surface-mediated pathway, where at the transition state the methane C-H bond is stretched, and the methyl interacts mostly with the dopant atom and the hydrogen with the lattice oxygen. The stronger hydrogen binding in the doped surfaces leads to a lower methane activation barrier; however, in some cases, the catalyst surface binds the hydrogen too strongly, poisoning the active site and making the catalyst inactive. The doped systems are largely constrained by the scaling relations, but sites closer to the optimum of the volcano plot exist, suggesting room for improvement.