I would have thought Caithness/Sutherland (the far north of Scotland). The total population of that vast area is roughly equivalent to an average sized UK town. When I cycled from Bonar Bridge to Inchnadamph back in July I only saw no more than a dozen cars in three hours, and that was on one of the main roads at the height of the tourist season.