As Andres implicitly pointed out, we may avoid diagonalization by working with ordinals directly.  We can appeal to Hartogs' Theorem to show that there is an ordinal $\beta$ that does not inject into $\omega$.  It is then easy to verify that the least such $\beta$ will be $\omega_1$ (i.e., the set of all countable ordinals).  Now using Choice, we can construct an injection $f: \omega_1 \rightarrow \mathcal{P}(\omega)$ by encoding each countable ordinal as a unique subset of $\omega$.  This can be done by letting $\langle f_{\alpha}| \alpha < \omega_1\rangle$ be a sequence such that each $f_{\alpha}$ is a bijection from $\omega$ into $\alpha$ and then defining $f(\alpha) = $ {$\langle m, n\rangle| f_{\alpha}(m) < f_{\alpha}(n)$} where $\langle \cdot, \cdot\rangle: \omega \times \omega \rightarrow \omega$ is the Cantor pairing function.  This completes the proof as if there were an injection from the powerset of $\omega$ (or the Reals) into $\omega$, then there would be an injection from $\omega_1$ into $\omega$.

It is worth noting that in a standard proof of Hartogs' Theorem, we use the fact that an ordinal cannot be a member of itself ($\beta \notin \beta$).  But because ordinals are well-ordered by the $\in$ relation, we can prove this fact without appealing to Foundation.