For any elementary topos $T$, there is a model category structure on $T$, whose cofibrations are the monomorphisms, and whose weak equivalences are the maps $X\to Y$ such that, either $Y$ is empty, either $X$ is non-empty (the fibrations are the split epimorphisms). In a topos, there exists an internal Hom (written here $\underline{Hom}$), as well as a subobject classifier $\Omega$: it comes with a map $t:1\to \Omega$ which is the universal subobject, in the sense that, for any object $X$ in $T$, pulling back along $t$ induces a bijection $$\text{ { subobjects of $X$} }\simeq \ Hom(X,\Omega)$$ Using the universal property of $\Omega$, the diagonal $X\to X\times X$ defines a map $X\times X\to \Omega$, whence an embedding of $X$ into its power object: $X\to P(X)=\underline{Hom}(X,\Omega)$. This gives you injective resolutions. We thus have a functorial fibrant replacement $X\mapsto I(X)$, where $I(X)=X$ if $X$ is empty, and $I(X)=P(X)$ otherwise (note that an object of $T$ is fibrant if and only if it is either empty, either injective). It remains to factor maps into a trivial cofibration (resp. cofibration) followed by a fibration (resp. trivial fibration). Let $f:X\to Y$ be a map in $T$. Such a factorization for $f$ is given by the map $X\to F\times Y$ followed by the projection $F\times Y\to Y$, for $F=I(X)$ (resp. $F=P(X)$). Hence we get a model structure on $T$, while we never used the axiom of choice.
Edit: and now, some genuine non sense (not abstract):
This model category structure on $Set$ is rather degenerate though. It seems that, to get model categories in general (on $Cat$ or on simplicial sets), we should change the definition of a model category by asking for lifting properties only internally: given maps $i:A\to B$ and $p:X\to Y$, $i$ has the (internal) left lifting property with respect to $p$ is the map $$Hom(B,X)\to Hom(X,A)\times_{Hom(Y,A)}Hom(Y,B)$$ is an epimorphism. In this way $Cat$ and $SSet$ remain model categories without the axiom of choice.
Edit: here, it seems I have been rather optimistic (see Mike comment below). I was thinking about working above an arbitrary topos (instead of sets), but, if we work externally in a setting without axiom of choice, then the lifting property suggested above is just the usual one, so that my remark seems to be (and is) silly. But what follows still makes sense.
Note that it is easy to get a structure of category of fibrant objects (in the sense of Brown, Abstract homotopy theory and generalized sheaf cohomology, Trans. Amer. Math. Soc. 186 (1974), 419–458) on $Cat$, which is sufficient to have calculus of fractions (up to homotopy), and gives you the abstract tools to explain the good behaviour of anafunctors. As for the size problems when we avoid the axiom of choice, maybe it would be worth looking for an "internal notion of size" to get that the Hom's of any homotopy category of a model category are small in some sense (but I had never thought seriously about this before).