Vector space bases without axiom of choice
The proof is not as constructive as one would expect.
I suggest that you take a look at Andreas Blass' paper in which he proved that the existence of bases implies the axiom of choice. From the proof it is easy to construct a counterexample.
The proof idea is to take a family of non-empty sets, and to show that there exists a choice function (not quite exactly, Blass goes through another equivalence first). Assuming the axiom of choice fails, there is a family of non-empty sets which doesn't have a choice function. From this you can construct a counterexample to the principle that Blass is using in his equivalence, and then you can easily construct the vector space which doesn't have a basis.
On the other hand, it is not very hard to construct specific models in which there are specific vector spaces without bases. $\ell_2$ doesn't have a basis in Solovay's model, and generally in models of $\sf ZF+DC+BP$ (where $\sf BP$ is the statement that every set of real numbers have the Baire property).
See also:
- Vector Spaces and AC