Electrically rechargeable zinc-air batteries have gained great attention in recent years due to their capacity to provide high energy density. The electrolyte has played a key role in the advancement of this technology and recently, aqueous chloride-based electrolytes have been demonstrated as a possible alternative to the traditional alkaline system. This study investigates, for the first time, the selection of an optimal bifunctional air electrode (BAE) formulation in two aqueous chloride-based electrolytes (pH4 and pH8) for zinc-air batteries. The effect of different MnxOy-based catalysts and carbon materials with different electrode formulations are electrochemically analyzed in the two electrolytic systems. The BAE formulation containing 20 wt% γ-MnO2, 70 wt% carbon nanotubes (CNT) and 10 wt% PTFE demonstrated the lowest overpotential, among all studied formulations, in both electrolytes. The cycling tests carried out using the selected electrode formulation, at both pH4 and pH8, reveal stable discharge-charge cycling over 400 h with an overpotential lower than 1.1 V. Moreover, the absence of manganese dissolution for the pH8 electrolyte is confirmed by ICP analysis, which overcomes the issue concerning the dissolution of manganese in more acidic media. Contrary to what is stated in conventional alkaline zinc-air batteries, where α-MnO2 is the most promising catalyst, this study highlights the potential of γ-MnO2-based BAEs when using aqueous chloride-based electrolyte.