What about the [Baire category theorem][1]? It implies that every complete metric space without isolated points is uncountable. But of course, *every* proof uses some construction or rather characterization of $\mathbb{R}$. I think Cantor's diagonal argument is not bad at all.

  [1]: https://en.wikipedia.org/wiki/Baire_category_theorem