So let's start with our very first two locations: The North and Winterfell.
GRRM has acknowledged that the inspiration for the Wall is indeed Hadrian's Wall. Of course. What else could it be? A giant wall built by the civilized empire to keep out the barbarians to the North.
However, as you can see, Hadrian's Wall, though heavily fortified in its day, is hardly the imposing Wall of the Night's Watch. More likely, Hadrian's Wall was focused on a. preventing simple cattle thievery (it's hard to drive cattle over a wall...even a short 10 footer) b. Customs and Taxation; and c. sheer Roman "look at what we can do, because we're ROME!"
Obviously that's not the stuff of fantasy epics, so with some imagineering, we get this:
So, having settled that the Wall is Hadrian's Wall, applying historical parallels, that makes the North Scotland. A fairly easy leap. Hadrian's wall divided the Scottish Highlands from the Lowlands, and the Highland Scots retained the Gaelic language (perhaps the "Old Tongue") and many of the more "barbarian" attributes of the Gaelic Celts.
Plus: Exhibit A