With the recognition of metal–air batteries as promising candidates for clean and efficient energy storage, the development of inexpensive and effective bifunctional catalysts for the oxygen reduction reaction (ORR) and the oxygen evolution reaction (OER) has become one of the most important topics in this field. Herein, we designed new composite catalysts consisting of a nanorod type Nd0.5Sr0.5CoO3−δ (NSC) perovskite and edge-iodinated graphene nanoplatelets (IGnPs) as bifunctional catalysts for ORR and OER. Interestingly, the simple application of ultrasonication endowed the catalyst with a fascinating morphology comprising cloud-like IGnPs on NSC nanorods (NSC@IGnP). Benefiting from the unique morphological features, NSC@IGnP provides superior bifunctional activities toward both ORR and OER, remarkable cell performance, and exceptionally high stability for hybrid Li–air batteries.