There is a weaker version of the first incompleteness theorem that is an almost trivial consequence of an insight from computability theory, namely of the result that
there exists a computably enumerable set that is not computable (*).
Consequence: the set of true first-order sentences (i.e. true about the 'real' natural number sequence) is not axiomatizable by a c.e. axiom set.
Unfortunately, most proofs of ($*$) have themselves a scent of self-referentiality hanging around them. However, you may want to check out 'simple sets'. Simple sets are c.e. and not recursive, and the standard textbook-proof of their existence is, to the best of my knowledge, the argument that comes closest to a non-selfreferential argument for ($*$).