How do I recover my Apple ID without access to old trusted devices or my trusted number.

It sounds as if you have set up two-step verification.

Then you just need your recovery key and you'll be all set.

If you can't sign in with two-step verification using your Apple ID - Apple Support

Without your recovery key and assuming you also have no access to a trusted device, you will never be able to use that Apple ID ever again.

As that link that sberman posted clearly states, if you've lost two or more of the required 2-step verification authentication tokens (password, trusted devices and/or your recovery key) then no, your AppleID cannot be recovered. You will have to make a new AppleID.

2-step verification is a great way to protect your AppleID, but you cannot expect it to be recoverable when you've forgotten every single one of the security verification features. You should have the recovery key safely stored somewhere. Since there are no security questions with 2-step verification, that recovery key is vital to recover the AppleID account.

If you know the password then you still only have one of the 2 pieces you need to recover the account. I would suggest calling Apple or going back to the Apple Store as you need to explain to them how the phone number of the sole trusted device has changed but that you still have that actual device.