Does a countably infinite power set exist?

Let $A$ be a set.

If $A$ is finite then so is $\mathcal{P}(A)$.

If $A$ is not finite then it has a countably infinite subset $B$, in which case $\mathcal{P}(B)$ is uncountable and thus so is $\mathcal{P}(A)$.

Can I say that given an arbitrary set its power set may be finite or uncountably infinite but never countably infinite?

Yes. To word it slightly differently, we have:

If $A$ is finite, then $\mathscr{P}(A)$ is finite.

If $A$ is infinite, then $\mathscr{P}(A)$ has cardinality strictly larger than $A$. This means $|\mathbb{N}|\le|A|<|\mathscr{P}(A)|$, so $\mathscr{P}(A)$ is not countably infinite.

This shows that we do not need the axiom of choice, which is used in your post to find a countably infinite subset of an arbitrary infinite set (and in mine in the same manner; see below).

Edit:

As the comments by bof and Noah indicate, the claim $|\mathbb{N}|\le|A|$ for infinite $A$ uses choice in the same manner as the argument in the OP. Indeed, to prove this, one finds a countably infinite subset and considers the inclusion map. Sorry for the major blunder! However bof's comment

To avoid the axiom of choice, I'd use a proof by contradiction: assume $|\mathscr{P}(A)|=|N|$, then $|A|<|\mathscr{P}(A)|=|N|$, so $|A|<|N|$, so $|\mathscr{P}(A)|<|N|$.

indicates that the statement is still true without choice.