Why do we need axiom of choice for this? The answerers on this question say that we need AoC (or some variant thereof) to prove that every infinite set has a countably infinite subset. In my view, choice is not needed but the answerers are much more experienced than me so now I'm not sure. 
For $S$ an infinite set we have $\aleph_0 \leq |S|$. Thus there exists an injection $f:\mathbb{N} \to S$. Let $I$ denote the image set and note $f:\mathbb{N} \to I$ is a bijection. Hence $I \subset S$ is countably infinite. 
Is there a mistake with this? Or am I somehow "implicitly" using AoC? 
 A: Your "implicit usage" is actually in the very first line: $\aleph_0\le|S|$ is equivalent to the definition of a Dedekind-infinite set, which is strictly stronger than an infinite set, which only means that it is not finite (not in bijection with an element of $\omega$). A set is defined to be Dedekind-infinite if $|S|=|S|+1$, or equivalently there is a bijection from $S$ to one of its proper subsets (or as mentioned, $\aleph_0\le|S|$).
It is true that any Dedekind-infinite set contains a countable subset. In ZF, it is possible that there exist infinite Dedekind-finite sets. If $S$ is infinite Dedekind-finite, then $|S|<|S|+1$, but $n<|S|$ for every natural number $n$. $|S|$ is incomparable with $\aleph_0$, so there are no countably infinite subsets of $S$.
A: Intuitevely you are making the following infinite process: given an infinite set $X$ you choose any $a_0\in X$; then you choose $a_1\in X_1$, where $X_1=X\setminus\{a_0\}$. For any natural $n$ you choose $a_n\in X\setminus\{a_0,\dots,a_{n-1}\}$. This may seem to work without Choice, but the trick is that you need to do this process $\omega$ times. It's like saying that theres some $f\in\prod_{n\in\mathbb{N}}X_n$. Therefore you need Choice. But you can weaken this to Countable Choice (cartesian product of countable many non-empty sets is not empty).
Hope this idea clears it up!
A: I believe it can't be proven in Zermelo-Fraenkel set theory that all infinite sets have a countably infinite subset. It can however easily be shown in Zermelo-Fraenkel set theory with the axiom of dependent choice that all infinite sets have a countably infinite subset. For each natural number n, there is a way to pick an element different from any of the elements you already picked so assuming the axiom of dependent choice, it follows that you can keep picking an element different from the ones you already picked for ever.
