I just got a new iPhone to replace my broken one. I can't really do much without signing into iCloud, which requires me to use a verification code. This can either be sent to some other trusted apple device of mine (no such device exists), or as a text to my phone (that won't work because I'm trying to set up my phone). So how can I sign in to iCloud?
Don't log in during set-up, but login afterwards using Settings. At that time you'll be able to request an authentication code via SMS.
iCloud only asks for a trusted device after you add and verify the other devices.
Best be would be to log in to your AppleID on a computer and check your options, perhaps adding a friend or relative's mobile temporarily. Once you’re set, you can then decide if two factor is right for you with only one device. Keep in mind, iPad and Mac can be trusted devices, too in addition to a phone.
If that fails, you may have to work with Apple support to see if you have indeed locked yourself out of your account. Hopefully there is a fail safe like the enrollment email that's active for two weeks where you can opt out or work through the recovery process.