Yes. The axiom of choice is needed in order to show that every vector space which is not finitely generated contains an infinite linearly independent subset.
The original consistency proof due to Lauchli (1962) was to construct a model in which there is a vector space that is not spanned by any finite set, but every proper subspace is finite.
Namely every collection of linearly independent vectors is finite.
If you have the axiom of dependent choice then you can actually perform the induction which you suggest and have a countably infinite set of independent vectors. But this is quite far from the full axiom of choice.
If one tries real hard, one can get away with just countable choice (which is strictly weaker than dependent choice). The argument is as follows:
Let $\cal A_n$ be the collection of all sets of linearly independent of size $n$, since the space is not finitely generated $\cal A_n$ is non-empty for all $n\neq 0$. Let $A_n\in\cal A_n$ be some chosen set. Again using countable choice let $A$ be the union of the $A_n$'s, and $A$ is countable so we can write it as $\{a_n\mid n\in\omega\}$.
Pick $v_0=a_0$, and proceed by induction to define $v_{n+1}$ to be $a_k$ whose index is the least $k$ such that $a_k$ not in the span of $\{v_0,\ldots, v_n\}$. This $a_k$ exists because $A_{n+1}$ spans a vector space of dimension $n+1$ so it cannot be a subset of $\operatorname{span}\{v_0,\ldots,v_n\}$.
The set $\{v_n\mid n\in\omega\}$ is linearly independent, which follows from the choice of the $v_n$'s.
Interestingly, Lauchli's example was of a space that every endomorphism is a scalar multiplication and as the above indicates this construction also contradicted $\mathsf{DC}$. In my masters thesis I showed that you can have $\mathsf{DC}_\kappa$ and still have a vector space which has no endomorphisms except scalar multiplication - even if it has relatively large subspaces.
If you take a look at the proof that the existence of a complement implies the axiom of choice then by a careful proof analysis one can construct a counterexample that is actually in a space which has a basis.
The proof of the algebraic principle goes through proving that the axiom of multiple choice holds, rather than the axiom of choice. The two are equivalent over $\sf ZF$, so it's fine. This version is as follows:
The axiom of multiple choice. Let $X$ be a family of pairwise disjoint non-empty sets, each having at least two elements. Then there exists a function $f$ whose domain is $X$ such that $f(x)$ is a proper finite subset of $x$, for all $x\in X$.
The proof of the direct complement begins by taking $X$ as above, and defining the following vector space: $$V=\bigoplus_{x\in X}F^{(x)}$$
Where $F^{(x)}$ is just the space of functions with finitely many non-zero values from $x$ into $F$. We also define $F^{(x)}_0$ to be the space $f\in F^{(x)}$ such that $\sum_{u\in x}f(u)=0$.
I will leave it to you to find a basis for this space (hint, $F^{(\bigcup X)}$). Now if we can find a complement to the subspace $W=\bigoplus_{x\in X}F^{(x)}_0$ then we can construct a function $f$ as above.
Begin now with a model where the axiom of choice fails, then the axiom of multiple choice fails, and we can find such $X$ where the vector space $V$ has a basis but $W$ doesn't have a direct complement.
Best Answer
Classically, they can be pretty simple: that is,
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.