iPhone stolen with Verizon - bought new iPhone with ATT. How do I download with my Apple ID and password but no cellphone since it was stolen?

There is!

1. Go to appleid.apple.com
2. Sign in with your Apple ID.
3. Select “Didn’t get a verification code?”, then select More Options.
4. You'll be redirected to iforgot.apple.com
5. Complete your account recovery request. Find out more about account recovery. 

See this link for further instructions

Two-factor authentication for Apple ID – Apple Support (UK)

Do you need a verification code?

See if anything here helps.  If necessary, you can use account recovery as explained in the link at bottom of the article.

Verification code - how to get one and sign in with two-factor authentication.   *

If you can get a code and sign in, you need to change/add the number on your Apple ID. Look in the Security section when signed in online. You may have to add the new number before you can remove the old number. After the change, allow up to 24 hours for the change to sync. Before trying to make the change, sign out of Messages/FaceTime on all devices/computers.

Apple ID - Manage