“If you lose your key and are still signed in on one of your devices, visit account.google.com to add or replace a key. Otherwise, submit a request to recover your account. Google may take a few days to verify that it’s you and restore your access.”
I trust that it would be (potentially much) harder than normal, but it still seems to be possible.