I have now found a textbook that provides a complete proof of the Burali-Forti paradox without making use of von Neumann's definition of ordinals: "Basic Set Theory" by Azriel Levy. Before providing von Neumann's definition, he works just on the assumption that some "order types" can be defined such that the order type of two well-ordered sets is identicall iff they are order-isomorphic. Based only on this assumption, and, importantly for my concern, without using the Axiom of Foundation, he shows that the class of ordinals cannot be a set.
Apart from usual proofs with diagonalization, have a look at model-theoretic proofs (Kotlarski's proof, Kreisel's left-branch proof, etc..), then there are some other proofs that formalize paradoxes (Kikuchi's, Boolos's, etc... there are about a dozen, most of them mentioned in Kotlarski's book).
If you don't want full generality ("for every rec. ax. theory T") then of course almost every proof in modern Unprovability Theory does not use any self-reference (you build a model of your theory by hands, using some unprovable combinatorial principle). Have a look at some easy recent accessible model-theoretic proofs of the Paris-Harrington Principle.
At the low end of the consistency strength spectrum (ISigma_n, PA, ATR_0), for theories that already have good classifications of their provably recursive functions, PH and other unprovable statements can also be proved unprovable using ordinal analysis (e.g. Ketonen-Solovay style), without using diagonalization tricks.
For higher ends of the strength spectrum (SMAH, SRP, etc), H. Friedman's highly technical results also don't use any diagonalization. This is a huge powerful machinery, and much new research is happening there.
MDRP theory gives interesting examples: have a look at the Jones polynomial expression: you can indeed substitute numbers into it and hit every consistency statement by its instances. There are similar ones for n-consistency for each n.
There is much more to say: this is a big subject, with huge bibliography. And, yes, much of the body of results in the subject is unpublished. I can give more pointers if necessary.
Best Answer
The Liar is the statement "this sentence is false." It is expressible in any language able to perform self-reference and having a truth predicate. Thus, $L$ is a statement equivalent to $\neg T(L)$.
Goedel proved that the usual formal languages of mathematics, such as the language of arithmetic, are able to perform self-reference in the sense that for any assertion $\varphi(x)$ in the language of arithmetic, there is a sentence $\psi$ such that PA proves $\psi\iff\varphi(\langle\psi\rangle)$, where $\langle\psi\rangle$ denotes the Goedel code of $\psi$. Thus, the sentence $\psi$ asserts that "$\varphi$ holds of me".
Tarski observed that it follows from this that truth is not definable in arithmetic. Specifically, he proved that there can be no first order formula $T(x)$ such that $\psi\iff T(\langle\psi\rangle)$ holds for every sentence $\psi$. The reason is that the formula $\neg T(x)$ must have a fixed point, and so there will be a sentence $\psi$ for which PA proves $\psi\iff\neg T(\langle\psi\rangle)$, which would contradict the assumed property of T. The sentence $\psi$ is excactly the Liar.
Goedel observed that the concept of "provable", in contrast, is expressible, since a statement is provable (in PA) say, if and only if there is a finite sequence of symbols having the form of a proof. Thus, again by the fixed point lemma, there is a sentence $\psi$ such that PA proves $\psi\iff\neg\text{Prov}(\langle\psi\rangle)$. In other words, $\psi$ asserts "I am not provable". This statement is sufficiently close to the Liar paradox statement that one can fruitfully run the analysis, but instead of a contradiction, what one gets is that $\psi$ is true, but unprovable. This is how Goedel proved the Incompleteness Theorem.