I reached level 12 in less than 8 hours played.
This guide (or rather notes) is especially helpful if you start in Durotar. I did this with 5 Orc Shamans.
The fastest way to level is probably to get level 8 with a 4-man crew and then grind through instances with a level 70 mage and later level 70 warrior. That way you could get level 60 with your crew in about 2 days.
Try to avoid all collection quests.
Most of this is related to the Starter Guides you can find on:
1. Getting your Earth Totem
Follow https://www.wow-pro.com/leveling_guides/durotar_leveling_guide_1-12_%28orc/troll%29, but skip the following quests:
Galgar’s Cactus Apple Surprise
Sting of the Scorpid
As a shaman you still have to gather the hoofs though. To unlock totem quest you need level 4. So get level 4 before you do the medallion quest.
As soon as you got your earth totem, go south and jump down to merchant coast.
2. Swim to Ratchet the head over to Crossroads and Camp Taurajo for the flight points
3. Go to Bloodhoof Village [Check Tauren Starter guide]
On your way to Bloodhoof Village get the quest The Ravaged Caravan from Morin Cloudstalker and finish it [54,48] and get follow ups:
- The Venture Co.
- Supervisor Fizsprocket
In Bloodhoof Village get all not-collection quests and also the collection quest where you have to gather only 1 item of 4 different beasts. Go to the bridge to the north and get the quest Kyle’s Gone Missing! from Ahab Wheathoof. Kill the gnolls [35, 61] and the beasts you need to the West of Bloodhoof Village. Go to Red Rock and do the killing quest. Go south and kill venture goblins and their boss. Turn in all quests.
4. Visit: Thunderbluff and Hearthstone back to Durotar starting point. Check Durotar Leveling Guide if you need help with the quests.
5. Go to Senjin Village: Get the killing quests. Do the Kolkar quest, west of the Village, head over to the Echo Isles and kill those trolls. Turn in quests in Senjin Village.
6. Go to Razor Hill: Do the quests Encroachment and Vanquish the Betrayers and the quest Dark Storms where you have to kill the goblin Fizzle [42,26] (level 12). Turn all in.
7. Take Zeppelin to Tirisfal. Do the Scarlet quest serie and combine them with the other killing quests there. It might be a good idea to set your hearthstone in the inn. I did the quest in the following order:
- At War With The Scarlet Crusade
- The Haunted Mills / Deaths in the Family
- Wanted: Maggot Eye
Then I turned them in and did At War With The Scarlet Crusade at the tower. I turned this one in and did:
- At War With The Scarlet Crusade, east of the Brill
- Rear Guard Patrol
Then I finished At War With The Scarlet Crusade, near Scarlet Monastery and headed west to Agamand Mills (there is a path to get up the mountain) and killed Dargol in the Agamand Family Crypt.
8. Take the teleporter to Silvermoon. Kill a Darnassian Scout [36, 61], loot his documents and turn in quest and get follow up. Kill the Dwarf and visit Fairbreeze Village.
9. Fairbreeze Village: Do the killing quests. Dont forget The Scorched Grove and to kill Old Whitebark. Also the Murlocs drop a quest item. After that you are ready for Farstrider Retreat. On your way kill Darkwraiths and Rotlimb Marauders, turn the quest in. Also visit Apprentice Mirvenda but only for turning in the quest. Dont help her any further.
10. Farstrider Retreat: Do as explained in Snowflakes guide. This part is only about killing mobs and doing some fast clicks. In terms of exp / h your crew will outperform every solo player
11. Back To Fairbreeze to warn folks. After that go to Runewarden Deryan an do his quest.
You should be level 13 by now. Lets go to Ghostlands. The problem with those quests here is, that require minimum levels close to the quest level. My goal here was getting level 15 to turn in Necklace quest (obtained in Windrunner Spire).
Only after this I wanted to get fire totem and do Ragefire Chasm. You might want to stay longer in Ghostlands but if you want to do Wailing Caverns and the main quest you have to some prequesting in the Barrens. For that your level shouldnt be beyond level or 17.
Set your hearthstone to Tranquillien.
Get the Quest: Fallen Courier. Probably you kill enough beasts while being in Ghostlands.
Get the Quest: Tomber Supplies, Suncrown Village and Anok’Suten (close to Suncrown Village)
1. Kill the spiders and Anok’Suten, turn them in in Tranquillien
2. Do Tomber Supplies quest (to get friendly with Tranquillien), turn in
3. Get: Goldenmist Village, Investigate An’daroth, Help Ranger Valenna, Trouble at Underlight Village, Culinary Crunch for your main (no need to share, or share later)
4. Well, investigate An’daroth and see whats going on in Goldenmist Village
5. Head on to Windrunner Spire while trying to finish Fallen Courier. Kill mobs till you get the necklace. Then kill Gnolls and return to Tranquillien, also turn in Fallen Courier.
6. Go to Ranger Valanna (69,15) turn in, dont get follow up
7. Go to Farstrider Enclave (72,32) get: bearer of plague and Spirits of the Drowned, finish and turn in both quests (first kill 5 lynx for bearer of plague, then do Spirits of the Drowned and after that the remaining 5 lynx for Bearer of Plague). You could also do the escort quest in the troll cave.
8. You should be close to level 15 now. Try getting level 15 by grinding or doing another quest, eg. Nightelfs plans. After getting level 15 you unlock to quests in Farstrider Enclave. The troll killing quest also got a follow-up. When you are done right click the necklace and turn the quest in. Then go to Undercity. Go to the Apothecarium.
There are 2 quests in Thunderbluff, 1 in Orgrimmar and 1 in Undercity. If you do the quest serie Hidden Enemies then you can get an additional quest for the Chasm but getting the required item 5 times is a very frustrating thing to do.
Get your fire totem and get all quests for Ragefire Chasm and finish them. While obtaining the fire totem you could already do the following quests:
First  Disrupt the Attacks, then at the same time:
- The disruption ends
- Supplies for The Crossroads
Do the quest serie, starting with the Forgotten Pool to get the main quest for the Wailing Caverns. You could also do the quest serie where you have to get the Heads of several Kolkar leaders and of course the 4 quests between Ratchet and Northhold Watch.
Grind in the Wailing Caverns until you are level 22.
Close to Cross Roads get the quest
Do the following quests in the southern barrens:
 Betrayal from within
 Quest serie of Gann, there is a collection quest involved. But the drop rate is good and there should be enough dwarves around. If you got a shaman visit Brine for the Water Totem. If you got cooking trained gather Dig Rats and later get and turn in a quest close to Crossroads at Grub.
Take the zeppelin to Undercity, go to the Sepulcher, set hearth stone there if you intend to grind in Shadowfang for some time. Get the quest  Berens Peril from Shadow Priest Allister. Go to approx. 60,74 and complete the quest. Now grind in Shadowfang up to level 24.
Head on to Hillsbrad Foothills. Get the quest  Time to Strike on your way to Tarrens Mill. Get the following quests:
WANTED: Syndicate Personel
Battle of Hillsbrad
Complete according James Guides:
The Rescue and
WANTED: Syndicate Personel
After that complete Battle of Hillsbrad. Do the follow up and kill Kalaba and her peasants. You can just go on with that quest serie and kill also the blacksmiths and after that the mobs you need in the council hall. After cleaning the city hall move on to the mines. We will do the last part of Battle of Hillsbrad later.
Do the following quests/areas in the following order (James guide might be helpful here):
Turn in the quests, that should ding you level 26.
In Felfire Hill:
 Destroy the Legion
 Never Again!
Head on to Camp Taurajo, get the quest Melor sends word. Get the follow up Steelsnap in Thunderbluff. Grind in Razorfen Kraul till level 27. Follow James guide for Thousand Needles (chapter ii and chapter iii). You should skip the quests where you need Purifying Earth and the one around the Boiling Pool (Sacred Fire). While being around get Tanaris and Feralas flight points also.
Grind in Monatery-Graveyard till level 30 (so you can obtain quest â€œThe Hammer may fallâ€). In Undercity get the quest â€œTo steal from thievesâ€. Fly to Tarrens Mill, set hearthstone there. Do the following quests:
Obtain Helculars Rod
Battle for Hillsbrad
The Hammer may fall
To steal from thieves
Call to arms
Then hearthstone back to Tarrens Mill. Turn in quests, fly to Undercity, turn in quests.
Grind in the monastery (Graveyard and Library till level 35).