If your definition of "$X$ is infinite" is
There is an injective map $i:\mathbb{N} \rightarrow X$
Then the theorem is trivial: take the image $i(\mathbb{N})$. However this question is often posed with a different definition of infinite: a set $X$ is infinite if it is not finite, i.e.
There exists no bijection $\{1,\ldots,n\}\rightarrow X$ for any $n\in\mathbb{N}$.
Surprisingly, building a countably infinite subset of $X$ with this definition is not as trivial as it sounds! Essentially your idea is correct: choose some $x_0\in X$, since $X$ is not empty ($\emptyset=\{1,\ldots,0\}$, so $X$ cannot be equal to it). Then choose some $x_1\in X$ such that $x_1\neq x_0$ since if there were none, $X$ would be in bijection with $\{1\}$, repeat this for $x_2, x_3$, etc.
This doesn't quite work: for each sequence $x_0,\ldots, x_n$ it's easy to build $x_{n+1}$ by contradiction, but it's quite hard to build the whole sequence $(x_n)_{n\in\mathbb{N}}$ uniformly. It's a problem of "swapping quantifiers":
$$ \forall n,\exists x_0,\ldots,x_n\ i,j\leq n, i\neq j\Rightarrow x_i\neq x_j$$
is not equivalent to
$$ \exists (x_n)_{n\in\mathbb{N}},\forall n, i,j\leq n, i\neq j \Rightarrow x_i\neq x_j$$
without the axiom of choice. With the axiom of choice this becomes quite easy, e.g. by using Zorn's lemma (I'll let you work out the details).
It is a surprising fact that some form of the axiom of choice is needed to show this equivalence. This type of counter intuitive "uniform choice" problem happens a lot when dealing with infinite sets, which is why it is crucial to always explicitly state which definitions you are using, and be very careful with your proofs!