I can't unfortunately help you with that because the accounts I'm moving both have "custom domain e-mail" set as account. However for verification it usually uses either other iDevice (so popups happen on phone etc.) and there's also option to have printed emergency access card and one can also set emergency contact details to off-icloud e-mails and phone numbers.

I'd say that getting access to account in iCloud was much easier than getting back to locked GMail account.