Even though this question is several months old, and you've probably committed to a route by now, I think this one deserves an answer for those who come across it down the road.
It's hard to make any good suggestions without information on what you're going to do with the data or how you need to handle/query it. Probably the most important thing you should ask yourself is: once this is all mapped, what do you want to be able to do with this data? Do you want to be able to see all streets in the USA or have an RSS feed of all streets in SF? Is this just for breaking down permalinks?
As I see it, here are your best options:
- Hierarchical custom taxonomy for region, with a CPT for street
- CPT for region and CPT for street, and connect them with Posts 2 Posts, as @Álex pointed out
- Custom MySQL table, with custom code backing it up
Without further info, one really can't suggest one over another, but I'd say in 90% of the time you'd be best off going with #1, 7% of the time #2, and 3% of the time #3. Don't hold me to the accuracy of that breakdown, though ;-)
I hope this helps you or someone else. If you did move forward on this project, it would be great to share what you ended up doing and how it's working out for you!