I leveled a worgen druid through the new "old" areas. After the worgen starter zones, I was 14 and did Darkshore and got around level 23 or so there. I then did Ashenvale, and got to around lvl 30. I started Stonetalon mountains, and around 10 quests in or so decided to switch to Eastern Kingdoms because I started to realize that I should probably work on getting Stormwind faction to get cheaper flying skills and training.
I started out in Northern Stranglethorn Vale (apparently it was split into 2 zones now), and around lvl 36 began to queue for dungeons, then queued them like mad and was level 41 by the time I realized I should probably finish Southern STV's quest chains (which is pretty epic, Booty Bay gets invaded, and I managed to find that rare purple parrot pet which I managed to sell for 7k gold).
Then I hit Western Plaguelands (btw, for Alliance there's a mage NPC that will port you there, so you don't need to foolishly run up there to get the flightpath first like I did), Eastern Plaguelands, Badlands, Searing Gorge, Burning Steppes, Swamp of Sorrows. Though I was 60 by then, I did Blasted Lands too, partly for the achievement, partly to get more xp before going to Outlands, and partly because I wanted to see how they redid that zone as well. I really like what the did to streamline questing and make it a little more interesting.
If you want, you could pretty much level all the way to 60 just doing dungeons too with Random Dungeon Finder, although you tend to get groups faster as a tank or healer. I thought about doing this, and with faction tabards you could gain rep with a faction from mobs there (which I found after my move to STV), but I wanted to quest more. The vast majority of quests now have the NPC's at the entrance of the dungeon so you can pick up quests there and finish them. But Outland/Northrend you still need to find the quests that take you to the dungeon first if you want to do those. Cataclysm usually has an NPC at the entrance with a quest, but some of them have pre-reqs that you need to do before you can get them, such as in Vashj'ir.



