Using Skolem functions, one can see in ZFC that a cardinal $\kappa$ is Jonsson iff there are no Jonsson algebras on $\kappa$. (I.e. every algebra of size $\kappa$ has a proper subalgebra of size $\kappa$) Is there a proof of this that doesn't use the axiom of choice?
As Asaf pointed out, you can generate Skolem functions anyways in this context. What I'm really looking for is if there is a proof that doesn't use Skolem functions. For instance if a set $X$ happened to be so that for every functions $f:[X]^{<\omega} \to X$ there is a set $A \subseteq X$ so that $\#A = \#X$ so that $f[[A]^{<\omega}] \neq X$, does that mean that every algebra on $X$ has a proper subalgebra in bijection with $X$?
Your language is countable, your structure is well-orderable.
This means that you can prove the existence of Skolem functions without appealing to choice. So the usual proof should work pretty much out of the box.