recover apple ID with change trusted phone number

You can start the formal account recovery process through Apple Support Account Recovery on Safari or via the Apple Support app on a borrowed device, though losing access to both your trusted phone number and account email makes verification strictly dependent on Apple's multi-day security waiting period. 

I assume your new phone is using the same phone number as your lost one, so the 2FA code will be sent to your new device. If you don't have cellular activated on your new device yet, then set up your device as new at first and at the end of the set up process is where cellular activation occurs. Once that is done, you can sign into your account using that 2FA code or reset your device to restore from your previous phones backup that you will now be able to enter that 2FA code.

It is unclear what role the email has in your setup, since the 2FA code is not sent to an email. You can turn 2FA back off if within the 2 weeks of turning it on, and that would be done with the email that had previously been sent to you, but it should not be necessary.

If unable to gain access using this method, then you are off to Account Recovery with those steps provided in the link below. Don't worry about the reference to an email, it is not needed at all. The only thing that email tells you is how long your waiting period will be and you can still find the waiting period by waiting 72 hours and looking on the iforgot website as detailed in the Support Article.

What to expect during account recovery - Apple Support