What's an example of a vector space that doesn't have a basis if we don't accept Choice?

Classically, they can be pretty simple: that is,

We can have a model $M$ of ZFC, with an inner model $N$ of ZF, such that there is a $\mathbb{Z}/2\mathbb{Z}$-vector space $V\in N$ such that $(i)$ $N\models$"$V$ has no basis" and $(ii)$ $M\models$"$V\cong\bigoplus_{\omega}\mathbb{Z}/2\mathbb{Z}$".

Of course, inside $N$ this characterization of $V$ won't be visible.

I almost forgot the classic: $\mathbb{R}$, as a vector space over $\mathbb{Q}$! I'd argue this is "more complicated" than the one above in certain senses, but in others its more natural.

As to why this happens: basically, consider a "sufficiently large" vector space $V$ with lots of automorphisms. Then, starting in a universe $M$ of ZFC which contains $V$, we can build a forcing extension $M[W]$, where $W$ is a "generic copy" of $V$. That is, $W$ is isomorphic to $V$, but all twisted around in a weird way. Now, we can take a symmetric submodel $N$ of $M[W]$ - this is a structure between $M$ and $M[W]$, consisting (very roughly) of those things which can be defined from $W$ via a definition which is invariant under "lots" of automorphisms of $W$ - specifically, invariant under every automorphism fixing some finite set of vectors! But as long as $W$ is sufficiently nontrivial, no basis (or, in fact, infinite linearly independent set) is so fixed.

Of course, I've swept a lot under the rug - what's a forcing extension? what exactly is $M[G]$? and why does it satisfy ZF? - but this is a rough intuitive outline.

Actually, in a precise sense, this is the wrong answer: I've just argued that it's consistent with ZF that some vector spaces not have bases. But, in fact, Blass showed that "every vector space has a basis" is equivalent to the axiom of choice! See http://www.math.lsa.umich.edu/~ablass/bases-AC.pdf, which is self-contained. Blass' construction actually proves that "every vector space has a basis" implies the axiom of multiple choice - that from any family of nonempty sets, we may find a corresponding family of finite subsets (so, not quite a choice function); over ZF this is equivalent to AC (this uses the axiom of foundation, though).

Blass argues roughly as follows. Start with a family $X_i$ of nonempty sets; wlog, disjoint. Now look at the field $k(X)$ of rational functions over a field $k$ in the variables from $\bigcup X_i$; there is a particular subfield $K$ of $k(X)$ which Blass defines, and views $k(X)$ as a vector space over $K$. Blass then shows that a basis for $k(X)$ over $K$ yields a multiple choice function for the family $\{X_i\}$.

So now the question, "How can some vector spaces fail to have bases?" is reduced (really ahistorically) to, "How can choice fail?" And for that, we use forcing and symmetric submodels (or HOD-models, which turn out to be equivalent but look very different at first) as above.

If we only assume $\sf\neg AC$, then there is no hope for us to find a specific example, because it might be that such vector spaces have cardinalities well beyond what we can describe.

However, if we assume some stronger negation of $\sf AC$, for example axiom of determinacy, then one example would be $\Bbb R$ considered as a vector space over $\Bbb Q$.

Of course, $\sf AD$ is a bit of an overkill here. Nonexistence of Hamel basis for $\Bbb R$ follows already from "all sets of reals are measurable", and I believe even "all sets of reals have Baire property", the latter being equiconsistent with $\sf ZF$. Hence it is consistent with $\sf ZF$ that $\Bbb R$ as a vector space over $\Bbb Q$ has no basis.

As for "why this happens", let me show that under measurability assumption there is no such basis. Under this assumption, it's clear that every function $\Bbb R\rightarrow\Bbb R$ is measurable. Now it can be proven that every measurable function $f:\Bbb R\rightarrow\Bbb R$ which satisfies $f(x+y)=f(x)+f(y)$ for every $x,y$ must be in fact linear. This is a result due to Sierpiński I believe (I would be grateful if someone has posted a reference in a comment). However, if we had a Hamel basis, we could easily construct a function satisfying this condition but not linear: we can arbitrarily assign values of $f$ to elements of the basis and then uniquely extend it to whole $\Bbb R$, so e.g. if we define $f$ to be zero on all but one element of the basis, we get a desired function, which we, however, have proven can't exist.