The issue is that induction only tells you that something is true for every finite integer.
For example, by induction we can prove that every natural number $n$ has exactly $n$ predecessors ($0$ is a natural number). Does that mean that there exists a natural number with infinitely many predecessors? No. It does not.
Similarly here. If $A$ is an infinite set, without the axiom of choice we can prove that for every $n$ there is a subset of $A$ of size $n$. But can we prove there exists a subset equipotent with $\Bbb N$ itself? No. That requires us more. That requires that the choices we made during the inductive proof were coherent with one another, which essentially tells us that there is some sort of choice function that we can work with.
And indeed, without the axiom of choice, it is consistent that there are infinite sets without countably infinite subsets. These are called Dedekind-finite sets.
Perhaps the following elaboration is going to clarify this issue. Let's look at what the inductive proof really does.
You start with the empty set, and you have $A$ to choose from. That gives you $|A|$ many choices for a first element in your sequence. Suppose that you managed to get through $n$ choices, that gives you $|A|-n$ many choices to continue, and that's fine, since $|A|$ is not a finite integer, we can always make at least one choice and continue the construction.
But what are we really constructing? It's a tree of options. We start with the root, which is the empty sequence. Then at each step, we have splitting according to our options. In this case, however, there are infinitely many splittings at each step.
The inductive construction simply tells us that we constructed a tree without maximal points. The axiom of choice tells us that this tree has a branch, which in turn can be translated into a countably infinite subset. But the existence of a branch relies heavily on the axiom of choice. Why would you choose the first element to be one and not another? How about the second element? There is no canonical preference to make here, in the arbitrary case.
So what happens is that without choice, you might end up with a tree that has no maximal nodes, but no infinite branches either.
(In Mitchell Spector's answer he discusses inductive definitions, in that case, there is a function which chooses "the next step", so the tree is in fact a unique branch, and everything is fine. But in the proof you suggest, there is no such function, you appeal to choosing arbitrary elements at each step.)
For every rational $q$ let $A_q^+=\{x\in A\mid x\geq q\}$ and $A_q^-=\{x\in A\mid x<q\}$. If for some $q$ both are uncountable, super. If not, what can you say about $A$ itself?
Now, you might wonder as to the use of the axiom of choice here, and it hides beneath the surface: in order to prove that every countable union of countable sets is countable, we have to use the axiom of choice.
Edit: Let $r=\sup\{q\mid A^-_q\text{ is countable}\}$ and $s=\inf\{q\mid A^+_q\text{ is countable}\}$.
If either $r$ or $s$ is not a real number (i.e., $\pm\infty$) then we get that $A$ is countable.
If $r>s$, take a rational $q$ witnessing that, then $A^-_q$ and $A^+_q$ are both countable, what do we get?
If $r<s$, take a rational $q$ witnessing that, then $A^-_q$ and $A^+_q$ are both uncountable.
Finally, if $r=s=q$, take an increasing sequence of rationals $r_n$ and a decreasing sequence of rationals $s_n$, both converging to $q$. Then $A\cap\bigcup_{p<q}A_p^+=A\cap\bigcup_{n\in\Bbb N}A^+_{r_n}$ is countable; and $A\cap\bigcup_{p>r} A^-_p$ is countable. Again, we get that $A$ is countable.
So if $A$ is uncountable, there is a rational $q$ such that $r<q<s$ and $A_q^-$ and $A^+_q$ are both uncountable.
Best Answer
It doesn't require the axiom of choice. Remove one point.
If you want a countably infinite subset of every infinite set, I think you need to use (or at least the usual proof uses) the axiom of countable choice.
However, maybe you are thinking of the condition of being Dedekind infinite, as mentioned in Adrián Barquero's comment. There you want not just an infinite proper subset, but a proper subset that is in bijection with the whole set. This can be proved using the existence of a countably infinite subset, so again uses countable choice.