When do we need the axiom of choice to prove the existence of a basis? Let $X$ be a set and let $\ell_X$ be the vector space of real-valued functions over the set $X$.
At what cardinality of $X$ do we need the axiom of choice to prove the existence of a basis of $\ell_X$? (Assuming that there is a threshold cardinality). Are there intermediate examples where proving the existence of a basis requires very non-trivial tools (but not the axiom of choice)?
 A: Clearly if $X$ is finite, then the $\mathbb{R}$-vector space $F(X,\mathbb{R})$ of maps from $X$ to $\mathbb{R}$ has a basis - namely, consisting of the indicator functions $$\delta_a: x\mapsto 0\mbox{ if $x\not=a$, } x\mapsto 1\mbox{ if $x=a$}\quad (a\in X).$$
As soon as $X$ becomes infinite, however, some choice is needed: it is consistent with ZF that there is no basis for the $\mathbb{R}$-vector space of maps from $\mathbb{N}$ to $\mathbb{R}$ - in fact, we can replace $\mathbb{R}$ here by $\mathbb{Z}/2\mathbb{Z}$! 
At the same time, there is no "moment" where full choice becomes needed: since choice can hold "up to a certain point" in the set theoretic universe yet fail later (that is, we could have every set of rank $<\alpha$ be well-orderable, but some non-well-orderable set of rank $\ge\alpha$), there's essentially never a "single instance" of, well, anything that implies full choice.
A: The answer would be that $\Bbb R^X$ has a Hamel basis exactly in the models where it has a Hamel basis.
Okay, that's a bit circular. But there's a good reason for this. Consider the case of $X=\Bbb N$, we already know that if every set of reals is Lebesgue measurable, or has the Baire property, then there is no Hamel basis for $\Bbb{R^N}$.
The problem is that we don't know quite "how much choice" is truly needed. We only know that it is somewhere between "all the choice" and "some of the choice". In other words, there is no easy-to-formulate-and-understand choice principle which gives you the correct provability power. Or at least, we don't know of one.
And it's even worse. Since the axiom of choice can start failing in a arbitrarily high stage of the von Neumann hierarchy, we can't even say something about the least stage where this fails. It could be the case that any $X$ that you ever imagined would have $\Bbb R^X$ is well-orderable, which means we can construct the basis using transfinite recursion, and yet, somewhere out there, in space, there is an $X$ such that $\Bbb R^X$ does not have a Hamel basis.
