Another idea, without changing the content or risking major bugging with random-layout dungeons, is simply to have random tasks. As an example, there can be a list of tasks for PvE (generally dungeoning,) PvP (focused on battlegrounds or doing PvP-like world events, such as "kill x number of PvP-flagged enemy targets in Y location") and professions (incentives to learn and improve them, or calls to make some number of a random item the player can make.)
Then you'd get one for each list; you could do one, and it'd net some considerable gold and a rep token you could use to improve a reputation with one or two factions based on where you used it. (For example, if these tokens gave 1200 rep, it might split 450 tauren, 450 orcs, 300 trolls in the Barrens, or 150 Hydraxian Waterlords, 1050 Cenarion Circle in Silithus.)
"Into the Unknown, With the Unknown" While not in a group, queue for a Random Dungeon and complete it.
"Answering the Call" Queue for a Random Dungeon while at least one role has the Call to Arms bonus, and complete it.
"Old World Reinforcements" Complete X specified "low level" dungeons.
"Assisting Our Allies" Complete X number of repeatable or daily quests for Y faction (needn't be contemporary.)
"Merely a Setback" Kill Kael'thas in Tempest Keep or Magister's Terrace!
"Thrice the Setback" Kill Keleseth in Utgarde Keep, Valanar in Naxxanar, and Taldaram in Ahn'kahet - or all three together in Icecrown!
"Call to Arms!" Queue for the Call to Arms battleground and win while doing at least X combined damage and healing.
"Anywhere, Any Time" Queue for a Random battleground and win while doing at least X combined damage and healing.
"The Task at Hand" Complete at least 3 different battleground tasks (that is, objective contributions, not just racking up damage and healing numbers) and win.
"Behind Enemy Lines" Kill at least 15 members of the enemy faction in X region. Player and PvP-marked non-player targets count toward this total.
"Black Gryphon Down" (85 only!!) Kill an enemy Flight Master. You may want to call for backup.
"In the Fields of Glory" Complete X World PvP objective. (For example, it could be Tol Barad, Wintergrasp, or one of the Outland objectives such as Auchindoun, Halaa, or Zangarmarsh --- or, for real bonus points, winning the Silithus gathering race, which totally still exists...)
"Expand Your Mind" (For those that have an empty profession slot or two, or are missing secondary skills) Attain Expert rank in a profession or secondary skill. Professions or skills currently at or above 75 skill rating do not count.
"Supply the Army" (For those that have a Crafting profession) The army needs skilled crafters! Create 5 of X item and help the cause!
"Dark Iron Artisan" Create one item while standing within 8 yards of the Black Anvil!
"Mithril Chef Azeroth" Complete the cooking and fishing daily quests in Dalaran, Shattrath, and any capital city of your faction.
"I See You Farming" (For those that have a Gathering profession) The army needs supplies! Gather 4 full stacks of X item! For the Faction!
"Deep Delver" Gather at least Y of X nodes from within dungeons! (Where X is possible for at least one dungeon; for example, cobalt in Utgarde Keep, or the mad herbalism that goes on in TK-Botanica.)