As Andres implicitly pointed out, we may avoid diagonalization by working with ordinals directly. We can appeal to Hartog's 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 Hartog's 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.