Let X be an infinite set. Is it possible to show the existence of a countably infinite subset of X without using the Axiom of Choice?

Short answer: No. By countably infinite subset you mean, I guess, that there is a 11 map from the natural numbers into the set. If ZF is consistent, then it is consistent to have an amorphous set, i.e., a set whose subsets are all finite or have a finite complement. If you have an embedding of the natural numbers into a set, the image of the even numbers is infinite and has an infinite complement. So the set cannot be amorphous. 


No. A set which has a countably infinite subset is called Dedekindinfinite. Clearly every Dedekindinfinite set is infinite; the statement that every infinite set is Dedekindinfinite is not provable in ZF (assuming ZF is consistent, of course). You don't need full AC, though. In fact, the equivalence isn't even as strong as countable choice. 


The following (nicely written) paper might be relevant: http://arxiv.org/abs/math.LO/0605779 Division by three Peter G. Doyle, John Horton Conway We prove without appeal to the Axiom of Choice that for any sets A and B, if there is a onetoone correspondence between 3 cross A and 3 cross B then there is a onetoone correspondence between A and B. The first such proof, due to Lindenbaum, was announced by Lindenbaum and Tarski in 1926, and subsequently `lost'; Tarski published an alternative proof in 1949. We argue that the proof presented here follows Lindenbaum's original. 

