Is it possible to show that an infinite set has a countable (infinite) subset, without using the Axiom of Choice?

Short answer: No.

By countably infinite subset you mean, I guess, that there is a 1-1 map from the natural numbers into the set.

If ZF is consistent, then it is consistent to have an amorphous set, i.e., an infinite 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 Dedekind-infinite. Clearly every Dedekind-infinite set is infinite; the statement that every infinite set is Dedekind-infinite 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.