picakhu: This was posted on MO and there were some interesting answers. I believe the answer I gave there avoids any hidden use of diagonalization. Other answers there are interesting and useful to think about even if, at the end, a diagonal argument is lurking.
Below is an abridged version of my answer there. It assumes some knowledge of ordinals.
In a more general fashion, the question can be restated as:
Is there a proof of Cantor's theorem that ${}|X|<|{\mathcal P}(X)|$ that is not a diagonal argument?
I learned the following in A. Kanamori-D. Pincus. "Does GCH imply AC locally?", in Paul Erdős and his mathematics, II (Budapest, 1999), 413-426, Bolyai Soc. Math. Stud., 11, János Bolyai Math. Soc., Budapest, 2002. It dates back to Zermelo's 1904 well-ordering paper.
a. It is enough to show that there is no injection $F:{\mathcal P}(Y)\to Y$ for any set $Y$.
b. If there is such an injection $F$ we can (definably from $F$) produce a pair $(A,B)$ with $A\ne B$ and $F(A)=F(B)$. In effect, Zermelo proved that:
For any $F:{\mathcal P}(Y)\to Y$ there is a unique a unique well-ordering $(W, \lt)$ with $W\subseteq Y$ such that:
- $\forall x\in W (F (\{y ∈ W \mid y \lt x\}) = x)$, and
- $F (W )\in W$.
We can then take $A=W$ and $B=\{y\in W\mid y\lt F(W)\}$.
c. Zermelo's theorem can be proved using the (set theoretic) recursion theorem and Hartogs theorem that for any set $A$ there is a least ordinal $\alpha$ does not inject into $A$. Neither uses diagonalization.