Isn't $H(\mathfrak c^+)$, the collection of sets whose transitive closures have cardinality at most $\mathfrak c=2^{\aleph_0}$, a model of your theory (but not the power set axiom)? The point is that a set of cardinality $\mathfrak c$ has only $\mathfrak c$ countable subsets.

EDIT: Colin actually asked whether this theory is stronger than ZF minus power set plus "the set of natural numbers has a power set". To get a model where $\omega$ has a power set but some sets don't have a set-of-all-countable-subsets, replace $\mathfrak c^+$ in my original answer with $\kappa^+$ where $\kappa$ is a singular cardinal, greater than or equal to $\mathfrak c$, and of cofinality $\omega$. So the proposed model consists of all sets whose transitive closures have size at most $\kappa$. From $\kappa\geq\mathfrak c$, it follows that the model contains the actual power set of the (von Neumann) natural numbers. From the fact that $\kappa$ has cofinality $\omega$, it follows that a set of size $\kappa$ has strictly more than $\kappa$ countable subsets. Therefore, some sets in the model, for instance $\kappa$ itself, don't have a set-of-all-countable-subsets in the model. (Note that each individual countable subset of $\kappa$ is in the model, so nothing other than the genuine set-of-all-countable-subsets of $\kappa$ can serve as the set-of-all-countable-subsets of $\kappa$ in the sense of the model.)

(By the way, I'm aware that, in this situation, we actually have strict inequality $\kappa>\mathfrak c$ because $\mathfrak c$ can't have cofinality $\omega$. I ignored that fact above, because it's not needed for the argument.)