My guys are 50 now (5 x Paladin). I definitely plan on mostly random dungeon running to 68 after using the intial Hellfire quests to gear up a little more first.

The only note of caution I have though, is 70 to 80. If you do it all via dungeons you're going to have issues with certain areas (Argent Crusade, Sons of Hodir for example) not being opened up and usable cause you never did the quests that opened them.