Without the axiom of choice, could there be a small category with two non-isomorphic skeletons?
Let $C$ be a small category and $S$ and $S'$ be two skeletons of $C$ (i.e., full subcategories containing exactly one object from each isomorphism class). Then, for any object $X$ in $S$, there is exactly one object $X'$ in $S'$ for which $X'$ is isomorphic to $X$. However, one needs to use the axiom of choice to choose an isomorphism between $X$ and $X'$ for all objects $X$ in $S$, and only then could one extend the mapping on objects to a functor $S \to S'$.