Here the hints were to use the facts that $ZF \vdash (\forall$ infinite$ A |A \times A| = |A|) \rightarrow AC$ and that there is a bijection between $\omega \times \omega$ and $\omega$.
My idea was then to simply consider the theory with a single function symbol $f$, where the theory says "$f$ is a bijection". Call this $T$. $T$ has a model, $\omega$, and by applying the upwards and downwards lowenheim skolem theorem, we can get models of arbitrary cardinality, and thus bijections on sets of arbitrary cardinality.
There are a few problems with this of course: one is the straightforward problem that not every set is accounted for in this manner, only the sets lucky enough to become models (and $ZF$ requires that for all sets $A$, $|A^2| = |A|$, to prove Choice). I was hoping to get around this by looking at the proof of this statement and notice that it only requires this to hold for cardinals or something, but that doesn't seem to be true. A subtler concern is that all this talk of cardinals is suspect to begin with in the absence of choice, and I'm not sure if I'm being too flippant with my use of cardinals in a choice-free setting.
Is my approach on the right track?
For reference, here's the 'cardinal free' version of Downward Lowenheim Skolem theorem:
Given an infinite structure $M$, then for all $A \subseteq M$, there is a $N \prec M$ such that $A \subseteq N$ and $|N| \leq |A| + \aleph_0 + |L|$
All references to cardinality here can be thought of choice free.