Hillsbrad, Stranglethorn, and Tanaris are the major zones known for pvp being a constant. It's just how it is, with the zone layout and quests. The advice I'd give anyone is to know that ahead of time, and try to squeeze out as much questing as you can before entering those zones so you have an edge in terms of character level before you get there.
When I leveled a pair of Ally characters on a different server, I did all of Teldrassil and Dun Morogh, all of Darkshore, Loch Modan, Wetlands, Stonetalon, and Ashenvale before looking for new quests and zones. Stonetalon and Ashenvale are fairly contested with horde but it's a matter of quest location and exposure time of being spotted by the enemy being in your favor. Once I had those done, I was over level for half of Duskwood but picked up some good experience there, and had no difficulties with 1000 needles (shimmering flats), Desolace, Arathi Highlands, and Stranglethorn.
It's a matter of being willing to burn some travel time to just keep questing hard even when quests turn green. It all adds up, and it's a big difference between entering Hillsbrad or Stranglethorn at the lowest level or being 4-5 levels over when you encounter that Horde that wants to gank you.