You can find encodings in the natural numbers of certain collections of subsets of $\mathbb{N}$. For example, as was pointed out by Henning Makholm, there is a very nice encoding of the collection of finite subsets of $\mathbb{N}$.
More generally, let $A$ be a recursively enumerable subset of $\mathbb{N}$. Let $T_A$ be a Turing machine that, on input $n$, halts if $n\in A$, and does not halt otherwise. Then we can encode $A$ by using the usual index of the machine $T_A$.
This encoding is not fully satisfactory. There are infinitely many Turing machines that halt on input $n$ iff $n\in A$. Thus every recursively enumerable set has infinitely many encodings. Moreover, there is no algorithm for telling, given two natural numbers, whether they encode the same set.
For more modest collections than the collection of recursively enumerable sets, there are far more satisfactory encodings. As a small and not very interesting example, consider the collection of subsets of $\mathbb{N}$ that are either finite or cofinite (their complement is finite). A small modification of the encoding of finite subsets will take care of the finites and cofinites. Basically, just use the even natural numbers for the finites. If you have used $2k$ to encode a finite, use $2k+1$ to encode its complement.
In addition, the elements of any countably infinite subset of the power set of $\mathbb{N}$ can, by the definition of countably infinite, be encoded using the natural numbers. However, by cardinality considerations, we cannot encode all the subsets of $\mathbb{N}$ using elements of $\mathbb{N}$.
Many (most) of the elements $q$ have an infinite number of elements. Then you cannot form the product of those elements. You have shown that the set of finite subsets of the primes is countable, which is correct.
Best Answer
I believe the discussion is transparent if we work with the set-theoretical version of Cantor's theorem. The theorem says that given any function $f:X\to P(X)$, the set $H(f,X)=\{x\in X\,:\, x\notin f(x)\}$ is not in $\operatorname{im}(f)$. Therefore, a proof that there is no surjection $X\to P(X)$ would be like this:
Now, the same argument doesn't work if we substitute $P(X)$ with $P(X)\setminus\{\emptyset\}$, because the claim $H(f,X)\in P(X)\setminus\{\emptyset\}$ in (3) may fail. In fact, $f(x)=\{x\}$ is an easy example of a function $f:X\to P(X)$ such that $H(f,X)=\emptyset$ and, moreover, there are bijections $X\to P(X)\setminus\{\emptyset\}$ if $\lvert X\rvert\le1$.
For the special case where $X=\Bbb N$ (or more generally $X$ Dedekind-infinite) a proof that there isn't a surjection $X\to P(X)\setminus\{\emptyset\}$ could be like this:
The second question about the "cardinality in-between" seems nonsense to me.