The hard-landing process Google has is both human-mediated (which does not mean "you're hand-held through the process by a human being") and also iterated over time. Nobody had to figure out precisely what the account recovery process for Google was going to be a priori, because Google is a trusted third party and can adapt its recovery procedures as it needs to.
And I don't think it's just a matter of Google being cheap. If they had thousands of CSRs with the technical ability to reset passwords, I imagine we'd have a lot more cases of stolen accounts, using social engineering or bribery (as we see with SIM swaps).