I recently got a new phone because I lost my old phone. I cannot sign into gmail because it does not recognize my new device. I have searched on google help with no help what so ever. How do I recover my account on my new phone?
Unless you specifically attached a recovery email to the accounts there is nothing you can do.
Always create accounts from a workstation and then attach a mobile number to the account after setting up the security for the account. That way you will be offered mpre recovery options in the future!