"All statements are false" is NOT false!?! We use the expression self-reference differently. When I say self-reference I mean (as I have explained earlier) that the definiens can not contain the definiendum. And I am not talking about Godel numbers and codings.
You restrict the universe of statements to a set of formulas of a given language. Even in this case the truth predicate is undefinable so the OP's sentence can't be formalized. Or if you formalize the truth predicate in a metalanguage then when talking about all statements you will only talk about all statements of the object language.
I think OP meant something much more general than statements of a fixed object language L when he was talking about all statements.
So either:
1) "All statements are false" is self-referential (as I mean it), or
2) if we assume Godel numberings and that the sentence talks about its Godel-number then
2a) we don't have a truth predicate defined or
2b) we have a truth predicate but then we have meta statements outside of the quantification range
of "All statements are false".
This is why it can't be formalized.
"But it's not, and is perfectly definable in, say, Robinson's Arithmetic."
But it is because "a" is the first letter of the alphabet and
"The statement with the least Godel number that does not contain the first letter of the alphabet." contains "a".
edit: "the definiens can not contain the definiendum" in an explicit definition.