How to set up multiple hierarchy taxonomy?
It's quite simple:


State-County-City hierarchy you have figured out
Create separate taxonomy for regions
Go to /admin/structure/taxonomy/*/fields and add a taxonomy field to terms in first tree. That way you will be able to assign cities, counties and states to regions


Later, you will have to switch to Views for display, as regular taxonomy pages will not be enough to display nodes by historical region - but that's for another question.