Proof of undecidability not by reduction from the halting problem The usual way of proving undecidability is by reduction from a RE-complete problem such as the halting problem, validity in first order logic, satisfiability of Diophantine equations, etc.

It is known that there are recursively enumerable, but undecidable problems that are not RE-complete, but these are artificial constructions (that is, sets that have been defined just for showing this "density" result).

How would one tackle proving undecidability without reduction from a RE-complete problem? Diagonalization?
One can show fairly directly that Kolmogorov complexity is not computable, see e.g. Sipser, 3rd edition, problem  6.23.