Rational design and synthesis of low-cost trifunctional electrocatalysts with improved stability and superior electrocatalytic activity for oxygen reduction reaction (ORR), oxygen evolution reaction (OER), and hydrogen evolution reaction (HER) are highly desirable but remain as the bottlenecks at the current state of technology. In this paper, the cobalt-iron (Co–Fe) composite supported on nitrogen-doped carbon nanotubes (CoFe composite/NCNTs) is synthesized. The intrinsic OER and HER catalytic activities of this CoFe composite/NCNTs composite are significantly improved with palladium (Pd) nanocluster decoration [Pd-coated (CoFe composite/NCNTs)]. The as-prepared Pd-coated (CoFe composite/NCNTs) catalyst exhibits excellent trifunctional electrocatalytic activity and stability due to the interfacial coupling between Pd and (CoFe composite/NCNTs). This catalyst is successfully employed in the water electrolysis cell as both OER and HER electrode catalysts, flexible rechargeable Zn-air battery as the bifunctional ORR and OER electrode catalyst. The cell voltage of this catalyst-coated electrodes requires only 1.60 V to achieve 10 mA cm−2 current density for water electrolysis cell, which is comparable to and even better than that of Pt/C and Ir/C based cell. The primary Zn-air battery using this catalyst shows a constant high open-circuit voltage (OCV) of 1.47 V and a maximum power density of 261 mW cm−2 in the flooded mode configuration. Most importantly, a flexible Zn-air battery with this catalyst runs very smoothly without a change in voltage gap during flat, bending, and twisting positions.