We study oxidative coupling of methane (OCM) on alkaline earth metal oxides (AEMO) 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 AEMO 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 interacts with lattice oxygen. The stronger hydrogen binding in the doped surfaces lead 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.