Indeed, COSHEP (more traditionally called the "presentation axiom" by constructivists) does seem to be what you need in order to get a model structure on Cat. That's true in a lot of similar cases: cofibrant objects are always "projective" in some sense, and you can't expect to get many projective objects in a category constructed from sets unless you started with enough projective objects in Set itself. So I don't expect that ordinary model category theory will be much good for anything at all if you don't have at least COSHEP. But, thankfully, model categories are not the be-all and end-all of homotopy theory, so we can still formally invert the weak equivalences (functors that are fully faithful and essentially surjective) to obtain anafunctors as a derived hom.

Indeed, COSHEP (more traditionally called the "presentation axiom" by constructivists) does seem to be what you need in order to get a model structure on Set, or Cat. That's true in a lot of similar cases: cofibrant objects are always "projective" in some sense, and you can't expect to get many projective objects in a category constructed from sets unless you started with enough projective objects in Set itself. So I don't expect that ordinary model category theory will be much good for anything at all if you don't have at least COSHEP. But, thankfully, model categories are not the be-all and end-all of homotopy theory, so we can still formally invert the weak equivalences (functors that are fully faithful and essentially surjective) to obtain anafunctors as a derived hom.