Here's a way to get started. Let $A$ be an infinite set. Let $F$ be a choice function on $\mathscr{P}(A)-\{\emptyset\}$. Now let $B$ be the collection of all finite subsets of $A$, and let $\emptyset\in B$ as well. Now let $f\colon B\to B$ be defined by $X\mapsto X\cup\{F(A-X)\}$.
By the recursion theorem on $\omega$, we know there exists a function
$h\colon\omega\to B$ such that $h(0)=\emptyset$ and
$$
h(n^+)=f(h(n))=h(n)\cup\{F(A-h(n))\}
$$
for every $n\in\omega$.
Claim. For every $m\leq n$, we have $h(m)\subset h(n)$. To see this, use induction. Let
$$
K=\{n\in\omega\ |\ m\leq n\implies h(m)\subset h(n)\}.
$$
Clearly $0\in K$, for if $m\leq 0$, then $m=0$, and obviously $h(0)\subset h(0)$. So suppose $n\in K$. If $m\leq n^+$ then either $m\leq n$ or $m=n^+$. In the first case, $h(m)\subset h(n)\subset h(n^+)$. In the second, $h(m)=h(n^+)$, so the conclusion follows either way. Hence $n^+\in K$, so $K=\omega$.
Now let $g\colon\omega\to A$ be defined as $n\mapsto F(A-h(n))\in A-h(n)$, which implies immediately that $g(n)\notin h(n)$. Try showing that $g$ is injective, which will prove that $g$ is surjective onto its range, which is a subset of $A$. Since $g$ is then a bijection from $\omega$ onto $\text{ran }g$, $\text{ran }g$ will be countable, and you'll have your result.
Added: To show $g$ is injective, suppose $m\neq n$, and let's suppose $m<n$. This means $m^+\leq n$, so by the above claim, $h(m^+)\subset h(n)$. Then
$$
h(m^+)=h(m)\cup\{F(A-h(m))\}=h(m)\cup\{g(m)\}.
$$
What does this tell you about $g(m)$ in relation to $h(m^+)$ and $h(n)$? Is it then possible that $g(m)=g(n)$? Why not? This proves $g$ is injective.
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.
Best Answer
First let us clear up the definitions, since there may be some confusion about them.
We say that a set $A$ is finite, if there is a natural number $n$ and a bijection between $A$ and $\{0,\ldots,n-1\}$. If $A$ is not finite, we say that it is infinite.
We say that a set $A$ is Dedekind-finite, if whenever $f\colon A\to A$ is an injective function, then $f$ is a bijection. If $A$ is not Dedekind-finite, we say that it is Dedekind-infinite.
What can we say immediately?
While in some low-level courses the definitions may be given as synonymous, the equivalence between finite and Dedekind-finite (or infinite and Dedekind-infinite) requires the presence of countable choice to some degree. This was shown originally by Fraenkel in the context of $\sf ZFA$ (where we allow non-set objects in our universe), and later the proof was imitated by Cohen in the context of forcing and symmetric extensions for producing a model of $\sf ZF$ without atoms where this equivalence fails.
Interestingly enough, Dedekind-finiteness can be graded into various level of finiteness, so some sets are more finite than others. For example, it is possible for a Dedekind-finite set to be mapped onto $\Bbb N$, which in some way makes it "less finite" than sets which cannot be mapped onto $\Bbb N$.