- edit -
Hi
Of course the proof can depend on how you defined "infinite", but, basically, we can always say that a infinite set minus a finite subset of its elements is still infinite (and by the way non empty) $\displaystyle (\star )$
Then, using the axiom of choice, you can choose an element $\displaystyle x$ in $\displaystyle S,$ and name it (in your head)* $\displaystyle a_0.$ Since $\displaystyle S_0:=S-\{x\}\neq\emptyset$, you can choose an element $\displaystyle y$ in $\displaystyle S_0$ and name it $\displaystyle a_1$, again $\displaystyle S_1:=S_0-\{y\}\neq\emptyset$ and you can choose... You can repeat a countable amount of times this operation using the axiom of choice and $\displaystyle (\star )$.
Finally, an injection $\displaystyle \mathbb{N}\hookrightarrow S$ would be $\displaystyle n\mapsto a_n,$ which proves what you wanted.
*Why in your head? Well we can rename the elements in $\displaystyle S,$ but that may not be very funny : if $\displaystyle S$ has already elements that are named $\displaystyle a_k$ for a $\displaystyle k\in \mathbb{N},$ that would be a problem.
One way to do would be to consider $\displaystyle S'=\{b_\lambda;\ \lambda\in S\}$ and say that $\displaystyle S\rightarrow S':\lambda\mapsto b_\lambda$ is a bijection, so we can use $\displaystyle S'$ instead of $\displaystyle S$ in the proof.