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 choice is that you need to actually choose one of them.  Or it hidden somewhere else?