Why am I being asked to verify billing information? An how do o do that?

You can download free apps, but you may need to have a valid payment method on file, even if the app you want to download is free. 

You can have a credit card / debit card on file and an Apple Account balance.

If you have set your Apple Account balance as your default payment method, your default payment method will be used first by Apple when you need to make a payment.

Free apps has also In-app pruchase.

See -> Buy additional app features with in-app purchases and subscriptions

Buy additional app features with in-app purchases and subscriptions

See also -> Apple Media Services Terms and Conditions

Legal - Apple Media Services - Apple

To verify your payment information, you need to Sign in to your Apple ID account page and edit / update your Apple ID details -> https://appleid.apple.com                                                     

• On the Sidebar click Payment methods -> then tap Payments Methods and tap Manage payment method.

or

If you need to change or update your Apple ID payment method

If you need to change or update your Apple ID payment method - Apple Support

• If you want to change your card, you need to add first the new card, then remove the old card.
• or if you want to use your Apple Account balance, you need to set your Apple Account balance as your default payment.

or

Add a payment method to your Apple ID

Add a payment method to your Apple ID – Apple Support (UK)

• If you want to change your card, you need to add first the new card, then remove the old card.
• or if you want to use your Apple Account balance, you need to set your Apple Account balance as your default payment.

See also the following Apple articles:

Payment methods you can use with your Apple ID

Payment methods you can use with your Apple ID – Apple Support (UK)

fyi: Not all credit & debit cards seem to work with App Store / iTunes Store, try a different one, or preferably a credit card.

If your card is not accepted as a paymenf method, you need to contact your bank.

Add money to your Apple Account balance

Add money to your Apple Account balance - Apple Support

If you have a valid payment method on file, instead of buying or order an App Store & iTunes gift card, you can Add money to your Apple Account balance anytime, no gift card needed, see -> Apple Gift Card - Apple (UK)

If you have followed all the steps and instructions and if you still need help, get support from Apple directly -> Get Support or call Apple in your region see -> Contact Apple for support and service or check -> here for more support and assistance.