Hey there!
I’m not a tax attorney or an accountant, so you may want to check this with them. I’d think that if only a billing address is filled in, that’s both the billing and shipping address.
Here’s an order that I made where the shipping address wasn’t different, so I only filled in the billing address. When WooCommerce made the order, it copied over the address so that it’s in both places:

Link to image: https://cld.wthms.co/0nMr2L
I would think that is sufficient to cover the requirement of having a shipping address for billing purposes.
As it is now, if a user chooses not to provide a shipping address my shop is NOT charging tax. Any ideas?
Taxes should be charged based on the address filled in – you can choose which address is used for tax purposes via WooCommerce > Settings > Taxes and then choose which address:

Link to image: https://cld.wthms.co/Rj4XCv
By default, this is set to the shipping address. While this should work as you need it to, it sounds like something on your site isn’t working correctly.
Could you please share a copy of your site’s System Status? You can find it via WooCommerce > Status.
Select “Get system report” and then “Copy for support”.? Once you’ve done that, paste it here in your response.