Low cost and green fabrication of high-performance electrocatalysts with earth-abundant resources for oxygen reduction reaction (ORR) and oxygen evolution reaction (OER) are crucial for the large-scale application of rechargeable Zn-air batteries (ZABs). In this work, our density functional theory calculations on the electrocatalyst suggest that the rational construction of interfacial structure can induce local charge redistribution, improve the electronic conductivity and enhance the catalyst stability. In order to realize such a structure, we spatially immobilize heterogeneous CoS/CoO nanocrystals onto N-doped graphene to synthesize a bifunctional electrocatalyst (CoS/ CoO@NGNs). The optimization of the composition, interfacial structure and conductivity of the electrocatalyst is conducted to achieve bifunctional catalytic activity and deliver outstanding efficiency and stability for both ORR and OER. The aqueous ZAB with the as-prepared CoS/ CoO@NGNs cathode displays a high maximum power density of 137.8 mW cm-2, a specific capacity of 723.9 mAh g-1 and excellent cycling stability (continuous operating for 100 h) with a high round-trip efficiency. In addition, the assembled quasi-solid-state ZAB also exhibits outstanding mechanical flexibility besides high battery performances, showing great potential for applications in flexible and wearable electronic devices.