Apply $\mathrm{Hom}(C,-)$ to your short exact sequence. It remains exact, so the identity map from $C$ to $C$ has at least one preimage. In fact, the splittings are exactly its preimages.
I would guess the problem with the axiom of choice is that you need to actually choose one of them. Or it hidden somewhere else?