Welcome to the wormhole.
A set which has a countably infinite subset is called Dedekind Infinite. It is not provable within Zermelo-Fraenkel set theory (ZF) that every infinite set is Dedekind infinite. This was demonstrated by Paul Cohen, who exhibited a model of ZF in which there is an infinite, Dedekind-finite set of real numbers. See Asaf's answer to my question for implications of this statement in analysis.
You do not need any form of the axiom of choice to prove that infinite equals Dedekind infinite, in the sense that one can construct models of ZF in which all infinite sets have countably infinite subsets but no form of the axiom of choice holds. However, if we do have some form of the axiom of choice available, even a weak form, then we can prove your statement.
Let me explain. The axiom of choice states that, given any collection $(A_i\;\colon\; i\in I)$ of nonempty sets, indexed by some set $I$, there exists a choice function picking out, for each $i\in I$, an element $a_i\in A_i$. In other words, we have a function $f\colon I\to\bigcup_iA_i$ such that $f(i)\in A_i$ for each $i$.
A well-known (but not easy to prove) consequence of the axiom of choice is the well-ordering theorem: given any set $A$, we can order the elements of $A$ in such a way that any nonempty subset of $A$ has a least element under the ordering. In fact, the well-ordering theorem is equivalent to the axiom of choice, since, given $(A_i\;\colon\;i\in I)$, we can define $f(i)$ to be the least element of $A_i$, under this ordering, giving us a choice function.
With this form of the axiom of choice, one can prove your statement as follows: given your set $S$, order it according to the well-ordering theorem. Then let $a_0$ be the least element of $S$, let $a_1$ be the least element of $S\setminus\{a_0\}$ and so on. This process will never terminate; otherwise, $S$ would be equal to $\{a_0,\dots,a_n\}$ for some $n$ and therefore would be finite.
That's all well and good, but the well-ordering theorem is a non-obvious theorem in set theory, and certainly isn't implicit in your argument. We shouldn't need to use it to prove this statement.
Thankfully, there is another way, and it actually involves a strictly weaker form of the axiom of choice. The axiom of countable choice is the same as the axiom of choice, except that we require the set $I$ to be countable. There are models of set theory in which the axiom of choice fails but still holds whenever the index set is countable, so countable choice is strictly weaker than full choice.
Here's how we prove your statement using only countable choice. Let $S$ be an infinite set. Then, for each $n=0,1,2,\dots$, let $S_n$ be the set of subsets of $S$ of size $2^n$.
We can show that each $S_n$ is non-empty using your argument (note that the axiom of choice is not required for a finite collection of sets, since we can proceed by induction): inductively pick elements $a_1,\dots,a_{2^n}$ from $S$; since $S$ is infinite, this process will not terminate and since we are only choosing finitely many elements, there are no dodgy set-theory issues.
Now, there are countably many $S_n$, so the axiom of countable choice tells us that there is a sequence $A_0,A_1,A_2,\dots$ of subsets of $S$ such that $A_n$ has size $2^n$ for each $n$.
Now, for each $n$, let $B_n$ be the set of elements of $A_n$ that are not contained in $A_0\cup\dots\cup A_{n-1}$. Since $A_n$ has size $2^n$, and $A_0,\dots,A_{n-1}$ have at most $1+2+4+\dots+2^{n-1}=2^n-1$ distinct elements between them, $B_n$ must be non-empty. By the axiom of countable choice again, we can choose a sequence $s_0,s_1,\dots$ with each $s_n\in B_n$. In particular, the $s_n$ are distinct. We have found a countably infinite subset of $S$.
We know, that the set $A$ is infinite, then it can be countable or uncountable, but regardless of which, the set $A$ contains an infinite countable subset. Suppose $B$ is such a set. So, $B=\{a_1,a_2,...,a_n,...\} \subset A$.
Defining $a_0 = b$, so $B'=B \cup \{b\}=\{b, a_1,a_2,...,a_n,...\} \subset (A~\cup \{b\})$ and the bijection $f: A \cup \{b\} \rightarrow A $ by
$$f(x) = \begin{cases}
x , &\text{ if $x \notin B'$} \\
a_{n+1} , &\text{ if $x \in B'$ }
\end{cases}$$
Note that, $f(b)=f(a_0)=a_1$, $f(a_1)=a_2, ...$
For the demonstration of the statement "If the set $A$ is infinity, contains an infinite countable subset", se below this ProofWiki.
Best Answer
Given an injection $f : S \to \mathbb{N}$, where $S$ is infinite, you can define a function $h : \mathbb{N} \to S$ by, for each $n \in \mathbb{N}$, defining $h(n)$ to be the element $s \in S$ for which $f(s)$ is the $n^{\text{th}}$ least element of $f(S) \subseteq \mathbb{N}$. This is possible because $S$ is infinite, so such an element $s \in S$ always exists, and $f$ is injective, so such an element $s \in S$ is unique.
It is straightforward to check that $h$ is bijective; then setting $g=h^{-1}$ gives you a bijection $g : S \to \mathbb{N}$.