OK, so the real problem is your phone is lost? If the lost phone is the one that gmail will send the verification to, then all is lost, not just the phone! DO not get a new number, but PORT your existing number to a new phone!
We understand that this is too late in this circumstance, but always create IMPORTANT accounts, such as email, and lesser important accounts, such as social media, on a landline workstation. A landline workstation can be laptop on wifi, or a desktop on wifi for that matter. The important thing; the account is created from a WIRED, NON-cellular network.
The provider can offer many ways to recover your account, if you create it in this manner. Always attach a recover email, such as a work, or another email that you will not forget the username and password to (because it SO important)!
After you have attached another email address in case of forgetfulness, now you can attach a mobile device to the account. Now, if you lose, break, or stop having access to your mobile device (non-payment of services), you can still recover your account!