Comment by threeseed

Why couldn't Google just have a shared key stored on each of the user's devices ?

The shared key could be backed up to Google's servers and encrypted using the user's password so in the event of a new device/flashing the shared key could be re-downloaded.

Then you only ask the user once for their password.