Consider the following sentences in a first-order language with one unary function symbol $f$:

$\forall x \exists y (fy=x)$

$\forall y\forall z(fy=fz\to y=z))$

$\forall x (\underbrace{f\dotsb f}_{n\mbox{ times}}x\neq x)$

so that any model of them is just a set equipped with a bijection with no finite orbits. This is the simplest list of axioms I could think of which has countably many non-isomorphic countable models and is uncountably categorial if you believe in Zorn's lemma, and this theory is therefore complete. Surely completeness of this theory doesn't depend on the axiom of choice. Does it?