This paper by Christian Elsholtz seems to be exactly what you're looking for. It motivates the Zagier/Liouville/Heath-Brown proof and uses the method to prove some other similar statements. Here is a German version, with slightly different content.
Essentially, Elsholtz takes the idea of using a group action and examining orbits as given (and why not -- it's relatively common) and writes down the axioms such a group action would have to fulfill to be useful in a proof of the two-squares theorem. He then algorithmically determines that there is a unique group action satisfying his axioms -- that is, the one in the Zagier proof. The important thing is that having written down these (fairly natural) axioms, there's no cleverness required; finding the involution in Zagier's proof boils down to solving a system of equations.
