Carbonized polypyrrole (PPy)-coated graphene aerogel (CPGA) was synthesized using graphene oxide and fresh pyrrole (Py) as raw materials in a hydrothermal process without any oxidant. After annealing at a high temperature, the as-prepared aerogel had a porous 3D network, contained a high percentage of nitrogen, and delivered a promising electrochemical catalytic activity. Most importantly, the annealing temperature had a significant impact on the electrochemical performance of the obtained materials. Among these products, CPGA-600 displayed the most positive onset potential and the highest peak current density for an oxygen reduction reaction (ORR). The electrocatalytic mechanism of the as-prepared materials for ORR in an alkaline electrolyte was also analyzed in detail. The results indicated that pyrrolic-N and highly graphitized carbon structures are mainly responsible for the enhanced ORR activity of metal-free N-doped carbon materials.