Probleme mit dem Passwortzurücksetzen bei Gmail

Hallo,
ich habe mein altes Handy geschrottet und mir ein neues Handy mit neuer Handy-Nummer zugelegt. Die alte Sim-Karte (Prapaid) hab ich zerschnitten, da auch kein Guthaben mehr drauf war.
Nun habe ich das Problem, dass ich nicht mehr auf meinen GMail-Account zugreifen kann, zumal ich mein Passwort vergessen habe. Ich hatte die alte Handy-Nummer zur Wiederherstellung hinterlegt. Aber auch eine weitere eMail-Adresse.
Nun bin ich die notwendigen Schritte zum Passwortzurücksetzen bei GMail durchgegangen und hab alles richtig beantwortet und bekomme nun folgende Nachricht:

Angaben stimmen nicht mit denen für xxx@gmail.com überein

Ihre Kontakt-E-Mail-Adresse: xxx@web.de

Die eingegebenen Informationen stimmen nicht mit unseren Unterlagen überein. Versuchen Sie, sich an einem Standort anzumelden, an dem Sie sich üblicherweise anmelden, z. B. zu Hause oder am Arbeitsplatz, und aktualisieren Sie die Kontoinformationen.

Was kann ich nun tun, damit ich wieder auf die alte Gmail-Adresse bzw. mein Passwort dort zurückgesetzt bekomme. Ich hatte ja auch alle Bilder bei Google Drive sowie in GMail meine ganzen Kontaktdaten und auf Google Play Store komme ich nun auch nicht mehr. Könnt ihr mir hier helfen?

kann es auch sein, da ich mich vom PC aus anmelden will, dass es hieran liegt:

Versuchen Sie, sich an einem Standort anzumelden, an dem Sie sich üblicherweise anmelden

Die Angaben die ich gemacht habe, stimmen - daran kann es eigentlich nicht liegen