Electrical energy storage and conversion is vital to a clean, sustainable, and secure energy future. Among all electrochemical energy storage devices, metal-air batteries have potential to offer the highest energy density, representing the most promising systems for portable (electronics), mobile (electrical vehicles), and stationary (micro-grids) applications. To date, however, many fundamental issues are yet to be overcome to realize this potential. For example, efficient catalysts for oxygen reduction reaction (ORR) and oxygen evolution reaction (OER) at the air-electrode are yet to be developed to significantly reduce the polarization loss in metal-air batteries, which severely hinders the rate capability, energy efficiency, and operational life. In this progress report, a brief overview is first presented of the critical issues relevant to air-electrodes in metal-air batteries. Some recent advancements in the development of non-precious catalysts for ORR in Li-air and Zn-air batteries are then highlighted, including transition metal oxides, low-dimensional carbon-based structures, and other catalysts such as transition-metal macrocycles and metal nitrides. New directions and future perspectives for metal-air batteries are also outlined.