Most civilized countries have strong authentication methods which are behind easy and cheap APIs for Google and others to use if they really care about restoring access.
In any case, lacking that, one could just walk into a Google office with a passport there. There are official ways to do authentication if these corporations really cared.