How do I sign in to iCloud when my phone was stolen? And I Have two factor authentication

You’ll need another trusted device. Or your phone number. Otherwise, you’ll need to start account recovery.

How to use account recovery when you can’t reset your Apple ID password - Apple Support

So what info should be enough to successfully recover account? Because a situation like the topic starter’s is very probable: you are traveling in a foreing country, iphone stolen together with sim card, so you don’t have phone number access to receive sms and no other trusted devices. So you remember your apple id email and password also but cannot login because neither registered phone no nor trusted devices are available!