I've seen a constructive proof based on induction that is awesome. But when I tried to prove it, I used a different approach. Can someone please verify my work? Thank you and any critic is highly appreciated!
It's a proven fact that $X$ is a countable set if and only if $\exists f : \mathbb{N} \rightarrow X$ surjective. Therefore if $X$ is not a countable set then $\nexists f: \mathbb{N} \rightarrow X$.
Since $X$ is infinite, it can be a (1) countable infinite set of an (2) uncountable infinite set.
(1) is trivial, since $X \subset X$, the theorem is proved for this case.
(2) $X$ is an uncountable infinite set. We can conclude by our previous statement that $\nexists f: \mathbb{N} \rightarrow X$ surjective. Therefore, for every function that maps $\mathbb{N}$ to $X$ there'll be elements of $X$ that is not image of any $n \in \mathbb{N}$. Let's define a set of those elements: $$ S:= \{x \in X | f(n) \neq x \text{ } \forall n \in \mathbb{N} \} $$ Now we can build a surjective function: $$ F:=f|_{f^{-1}(X\setminus S)} : f^{-1}(X \setminus S) \subset \mathbb{N} \longrightarrow X \setminus S $$ And by axiom of choice we can change the domain of $F$ by selecting for every $x \in X \setminus S$ only one element of $f^{-1}(X \setminus S)$. That'll make $F$ a bijective function. Let $\overline{F}$ be that modified version of $F$ and $\overline{\mathbb{N}}$ be the modified version $f^{-1}(X \setminus S)$. Now we have: $$ \overline{\mathbb{N}} \subset f^{-1}(X \setminus S) \subset \mathbb{N} \rightarrow \overline{\mathbb{N}} \subset \mathbb{N} \\ \overline{F} : \overline{\mathbb{N}} \longrightarrow X \setminus S $$ It's also a proven fact that every subset of a countable set is countable. Since $\mathbb{N}$ is countable, then $\overline{\mathbb{N}}$ is countable. By definition of countable set, we know that $\exists g: \mathbb{N} \rightarrow \overline{\mathbb{N}}$ bijective. Finally we can create a composition of functions to make a map from $\mathbb{N}$ to $X \setminus S$: $$ h := \overline{F} \circ g : \mathbb{N} \rightarrow X \setminus S $$ Since the composition of bijective functions is bijective, $h$ is also bijective and therefore $X\setminus S \subset X$ is countable.
From your statement "every subset of a countable set is countable", I presume you're using the term "countable" to include all finite sets, including the empty set. But with that definition, both (1) and (2) are trivial, because $\ \emptyset \subset X \ $. So, while I think your proof does work, it's kind of like using a sledgehammer to crack a nut.
A more interesting question is how to prove that any infinite set contains a countably infinite subset. In that case you would need to modify your proof to choose a function $\ f:\mathbb{N}\rightarrow X\ $ with an infinite range, and, as vxnture points out in his comment, simply asserting the existence of such a function would amount to begging the question. Nevertheless, I don't think it would take much more to adapt your proof to the countably infinite case. The existence of an injective function $\ f:\left\{1,2,\dots,n\right\}\rightarrow X\ $ is relatively trivial, and so you should be able to use Zorn's lemma to prove the existence of an injective function whose domain is the whole of $\ \mathbb{N}\ $, and whose range is a subset of $\ X\ $.