Although platinum and platinum alloys (e.g. PtNi and PtCo) are widely regarded as the best catalysts for ORR at present, they are expensive and still suffer from technical drawbacks. Recently, the exploration of Pt-free or even metal-free ORR catalysts including heteroatom-doped carbon nanomaterials is very active in the electrochemistry and carbon research communities. Previous investigations have employed five main dopant elements (i.e. nitrogen, boron, phosporus, sufur, and selenium), with majority of these studies concluding that nitrogen, especially when doped in a specific manner, shows the most positive effect in improving the catalytic activity of carbon. In this study, we explore a new set of dopant atoms (alkali, alkaline earth, and halogen atoms) for the two-dimensional graphene structure (both in the buckled and planar configurations) and look at the changes in the geometric and electronic structures via density functional theory (DFT) calculations. We also qualify and quantify the stability and nature of the substitional doping on graphene and observe the trends for various properties for each elemental group. For instance, the doping of alkaline-earth atoms on the graphene structure, which has been unexplored so far, modifies the electronic properties and consequently the oxygen adsorption energetics. We found that novel properties such as semi-metallic properties emerge after substitutional doping except with beryllium, pointing to the possibility that these doped materials can be used not just in electrochemical but also in catalytic and electronic applications.