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.)
The naive idea that you have now is using Dependent Choice. The choice of $x_1$ depends on the choice of $x_0$, and so on. You would have avoided choice if you had a unique choice to make for $x_1$, etc., but in that case you already have a countably infinite subset which is circular. The complicated approach is the correct one.
Choose a set of size $n+1$, for each $n$. Here we use choice from the family of sets $\{[X]^{n+1}\mid n\in\Bbb N\}$, where $[X]^k$ is $\{X_0\subseteq X\mid k=|X_0|\}$. None of the $[X]^{n+1}$ is empty, since $X$ is infinite.
For each of these sets choose an enumeration, that is a bijection between the set and $\{0,\dots,n\}$. Here we again use choice: if $X_n$ is the $n$th chosen set, then $S_n=\{f\colon\{0,\dots,n\}\to X_n\mid f\text{ is a bijection}\}$ is non-empty for all $n$.
Now recursively, pick the smallest in said enumeration which hasn't appeared in your collection yet, such smallest exists because at the $n$th step you've collected $n$ elements, but the set has $n+1$ elements.
This does not require any choice, since the enumerations are already given. So we can specify "smallest" and this is a unique element from each $X_n$.
This is just a cleaned up version of your idea. But the point is that this only uses Countable Choice, since we only used it to choose the sets and the enumerations (which we can choose in a single go, actually, by choosing an injection from $\{0,\dots,n\}$ into $X$ for each $n$).
Alternatively, you can choose $X_n$ to have size $(n+1)^{n+1}$, then $Y_n=X_n\setminus\bigcup_{k<n}X_k$ is always non-empty, and then we can apply choice to $\{Y_n\mid n\in\Bbb N\}$.
(Again, Countable Choice is needed to get these $X_n$'s as well as choosing from the $Y_n$'s.)
Best Answer
Yes, given a countable $A$ there is a sequence $f$ where all of them are $\le^*$ than $f$. We set $$f(1)=f_1(1)+1\\ f(2)=\max(f_1(2),f_2(2))+1\\ f(3)=\max(f_1(3),f_2(3),f_3(3))+1\\ f(n)=\max_{i=1}^n(f_i(n))+1$$ This is greater than the first sequence starting at $1$, greater than the second starting by $2$, greater than the $n^{th}$ starting by $n$. Each of the $\max$ functions has a finite list of arguments, so is well defined. Diagonalization wins again.