Is axiom of choice necessary for proving that every infinite set has a countably infinite subset? Is it possible to prove the following fact without axiom of choice ?
" Every infinite set has a countably infinite subset". 
Can it be proved that axiom of choice is necessary here ?
 A: If the definition for a set $A$ being infinite is $\exists f: \omega \to A$ injective, then in any model of ZF you can find a countably infinite subset of $A$ by taking the range of $f$ whose existence follows from replacement.
However, if the definition is $A$ is not finite, namely, there exists no bijection from $A$ to any $n\in \omega$, then the statement does not follow from ZF. In fact, in the model obtained by adjoining $\omega$ many Cohen reals (the forcing poset is $Fn(\omega\times\omega, 2)$ finite functions ordered by inclusion) then in its symmetric submodel $(HOD[G\cup \{G\}])^{M[G]}$, i.e. the class of hereditarily ordinal definable elements from $G\cup \{G\}$ in M[G] (which is a model of ZF), there exists a set that does not have countably infinite subset in the model $(HOD[G\cup \{G\}])^{M[G]}$, i.e. the set of Cohen reals $\{C_i: i\in \omega\}$ where $C_i(j)=G(i,j) \forall i,j\in\omega$. The reason is really that these Cohen reals can easily be permuted given finite information (aka the forcing is weakly homogeneous). You can refer to Jech's book on set theory for more details (there should be a chapter about symmetric submodes).
A: In very short terms (you are allready overwhelmed by good answers of experts): 
$$\omega\leq_{1}A\implies\neg A<_{1}\omega$$ 
Or in words:$$A\text{ is Dedekind-infinite}\implies A\text{ is infinite}$$
But for the converse you need a weakened form of AC. 
The axiom that every countable set has a choice-function (denoted as CC) will do.
This axiom implies that: $$A\leq_{1}\omega\vee\omega\leq_{1}A$$
A: This cannot be proved without the axiom of choice.  A set with no countably infinite subset is called a Dedekind-finite set.  An equivalent characterization is that the set is not in one-to-one correspondence with any proper subset of itself.  This condition is equivalent to finiteness in ZFC but not in ZF.  (See https://en.wikipedia.org/wiki/Dedekind-infinite_set and the references there for more information.)
A: First let us clear up the definitions, since there may be some confusion about them.
We say that a set $A$ is finite, if there is a natural number $n$ and a bijection between $A$ and $\{0,\ldots,n-1\}$. If $A$ is not finite, we say that it is infinite.
We say that a set $A$ is Dedekind-finite, if whenever $f\colon A\to A$ is an injective function, then $f$ is a bijection. If $A$ is not Dedekind-finite, we say that it is Dedekind-infinite.
What can we say immediately?


*

*Every finite set is Dedekind-finite, and every Dedekind-infinite set is infinite.

*$A$ is Dedekind-infinite if and only if it has a countably infinite subset if and only if there is an injection from $\Bbb N$ into $A$.

*Equivalently, $A$ is Dedekind-finite if and only if it has no countably infinite subset if and only if there is no injection from $\Bbb N$ into $A$.


While in some low-level courses the definitions may be given as synonymous, the equivalence between finite and Dedekind-finite (or infinite and Dedekind-infinite) requires the presence of countable choice to some degree. This was shown originally by Fraenkel in the context of $\sf ZFA$ (where we allow non-set objects in our universe), and later the proof was imitated by Cohen in the context of forcing and symmetric extensions for producing a model of $\sf ZF$ without atoms where this equivalence fails.
Interestingly enough, Dedekind-finiteness can be graded into various level of finiteness, so some sets are more finite than others. For example, it is possible for a Dedekind-finite set to be mapped onto $\Bbb N$, which in some way makes it "less finite" than sets which cannot be mapped onto $\Bbb N$.
A: Yes, some part of the axiom of choice is needed. In the absence of the axiom of choice it's consistent that there be an infinite, Dedekind finite set, and such a set admits no injection from $\Bbb N$.
