Hola saludes;
En este caso debes llamar a apple eso lo haces por medio de una aplicación llamada soporte de apple, te contactas y te dan las instrucciones, normalmente la forma de recuperar estas cuentas e por medio de la siguiente pagina:
https://iforgot.apple.com/es/password/verify/appleid
como comentas que ya te contactaste con soporte, me gustaría saber mas detalles de la solución que te brindaron.
Por otro lado aunque no tengas acceso al correo que supongo lo tenias vinculado a tu cuenta de iCloud la que cuenta de gmail, si respondes las preguntas puede que logres recuperar tu cuenta.
Asi mismo supongo que la protección antirrobo no estaba activa, esta funcion no permite que ninguna persona en el lapso de una hora pueda realizar ningún tipo de cambios y se pueda rápidamente llamar a apple para notificar esta novedad.
Quedo atento.