It happened to me when I changed country and phone number, I couldn't identified my iCloud account.

I just follow the instructions on the login page that I did not have my device with me, and just entered my Recovery Key that was given to me when I setup 2FA.

It's as simple as that.

Mind you I use a password manager and keep all my login information in it.