Medium:

Waist:
Storm Lord's Girdle - http://www.wowhead.com/?item=31138
Note - this is a BOE world drop, so if you have the cash and they are available on the AH by them. Otherwise there are no decent mail belts until level 64. Available for both Horde & Alliance.
Otherwise your next best bet would be:
Marsh Survivalist's Belt - http://www.wowhead.com/?item=25534
Quest Line:
Watcher Leesa'oh - http://www.wowhead.com/?quest=9697
Note - Needs friendly rep with Cenarion Expedition to become available
Observing the Sporelings - http://www.wowhead.com/?quest=9701
Note - Just need to go to coords 15,60 to complete quest.
A Question of Gluttony - http://www.wowhead.com/?quest=9702
Note - Gathering quest from quest items on ground at Quagg Ridge.
Stealing Back the Mushrooms - http://www.wowhead.com/?quest=9709
Note - Gathering quest - quest items on ground spawn a mob when looted, quest items can also be looted from mobs.


Hard:

Chest:
Stormstrike Vest - http://www.wowhead.com/?item=31719
Quest Line:
Bonechewer Blood - http://www.wowhead.com/?quest=10450
Note - Gathering quest, drop rate about 40%, mobs just outside Thrallmar
Apothecary Zelana - http://www.wowhead.com/?quest=10449
Note - Just talk to the NPC near Reaver's Fall to complete, then to the nearby Wind Rider for a free ride to Spinebreaker Ride (if you don't already have the FP)
Boiling Blood - http://www.wowhead.com/?quest=10538
Note - Gathering quest, and a long one. Drop rate on the blood is about 30%, but you need 12 for each toon. You then need to covert each blood to boiled blood at the cauldron at 65,71. Each conversion will spawn a number of low health bugs that will eventually start attacking you. Magma totem will help a lot here.
Apothecary Antonivich - http://www.wowhead.com/?quest=10835
Note - Head back to Thrallmar and talk to the NPC to complete.
A Burden Of Souls - http://www.wowhead.com/?quest=10864
Note - The Orcs along the Path Of Glory will give you the required souls for the quest
The Demoniac Scryer - http://www.wowhead.com/?quest=10838
Note - Use the shard at the base of Hellfire Citadel, near the PvP area. There's a nice monster-free area there.
Report To Nazgrel - http://www.wowhead.com/?quest=10875
Note - Just talk to the NPC to complete.
The Foot Of The Citadel - http://www.wowhead.com/?quest=10876
Note - You need to kill Gorax and then place the banner on his corpse. This will summon the Hand of Kargath (63 Elite) along with 2 non-elite adds. The elite likes to charge a lot, and hits fairly hard. Make sure you clear the area around Gorax before you kill him and start the event.

Hands:
Verdant Handwraps - http://www.wowhead.com/?item=28070
Quest Line:
Crimson Crystal Clue - http://www.wowhead.com/?quest=10134
Note - To start this quest you need a crystal that drops from the Raging Colossus's (62-63 Elites) north of Cenarion Post. You should get one of you do the quest Colossal Menace.
The Earthbinder - http://www.wowhead.com/?quest=10349
Note - mob will be summoned by the NPC, kill it and talk to her to complete the quest.
Natural Remedies - http://www.wowhead.com/?quest=10351
Note - Make sure the clear the Raging Colossus's from around the summoning area, as the summoned mob can knock players back quite far, and aggroing multiple mobs will mean a wipe. Wacth out for the adds spawned when the mob gets low on health (Raging Colossus also have this annoying ability). Chain Lightning and Fire Nova Totems work well here.

Totem:
Totem of Lightning - http://www.wowhead.com/?item=28066
Quest Line:
Colossal Menace - http://www.wowhead.com/?quest=10132
Note - Ragin Colossus's will spawn adds as their health depletes (up to 3 total). While doing this quest you should get the drop (A crystal) to start Natural Remedies quest line for the hands.


Totem of Impact - http://www.wowhead.com/?item=27947#comments
Quest Line:
Hellfire Fortifications - http://www.wowhead.com/?quest=10110
Note - Either repeat this daily quest 5 times to get the marks, or get killing blows in the PvP areas in Hellfire Peninsula & Zangramarsh


Trinkets:
Vengeance of the Illidari - http://www.wowhead.com/?item=28040
Note - If you have done the quests for the chest piece and th leg piece, you will have already done most of the quest line to get this item.
Quest Line:
Through the Dark Portal - http://www.wowhead.com/?quest=9407
Arrival in Outland - http://www.wowhead.com/?quest=10120
Journey to Thrallmar - http://www.wowhead.com/?quest=10289
Report to Nazgrel - http://www.wowhead.com/?quest=10291
Eradicate the Burning Legion - http://www.wowhead.com/?quest=10121
Note - these 4 quests involve entering the portal to outland, flying to Thrallmar and speaking to a few NPC's - should be able to complete them very qucikly.
Felspark Ravine - http://www.wowhead.com/?quest=10123
Note - kill 3 types of mobs near the quest giver. Easy!
Forward Base: Reaver's Fall - http://www.wowhead.com/?quest=10124
Note - just go and speak to the NPC to complete. Easy!
Disrupt Their Reinforcements - http://www.wowhead.com/?quest=10208
Note - Gather the runes from mobs on one toon, as using them to disable the portal updates the quest for the whole party. Easy!
Mission: Gateways Murketh and Shaadraz - http://www.wowhead.com/?quest=10129
Note - Bombing run quest, have to do indivually with each toon.
Mission: The Abyssal Shelf - http://www.wowhead.com/?quest=10162
Note - Bombing run quest, have to do indivually with each toon.
Return to Thrallmar -http://www.wowhead.com/?quest=10388
Note - Talk to Nazgrel in Thrallmar to complete
Forge Camp: Mageddon - http://www.wowhead.com/?quest=10390
Note - Kill 10 mobs plus a named mob - easy!
Cannons of Rage - http://www.wowhead.com/?quest=10391
Note - Cannons can be found just behind Thrallmar - kill 3. Easy!
Doorway to the Abyss - http://www.wowhead.com/?quest=10392
Note - Kill the named mob for the quest item, then use it on the nearly legion portal.
Cruel's Intentions - http://www.wowhead.com/?quest=10136
Note - Watch for Infernals that spawn when he's 75% health. He cast's a lot, grounding totem will be your friend here.