Context
I would like to get Google Maps API key for free usage (below 5000 per year hits), but when I follow the instructions, it seems that providing billing information is mandatory.
Question
What am I missing, or is it really impossible to have Google Maps on a page without providing billing info?
Yes you need to setup a billing account, there is no way around it these days. As long as you keep under the free tier it doesn't really matter.
Also their pricing examples are counted monthly so the things that have 5 000 hits in their pricing is per month not per year.