I have run so many people not including my own 6 twinks thru instances at 39 for xp/loot its not even funny. 1000 times thru sm (mostly just cath for xp runs) is not an exaggeration nor is 1000+ revelosh runs.
First, dont use the ogron's sash, stop gimping your armor, warriors are weak enough at 39. Farm the rare in RFD for the boar champion's belt. Second, SM will easiliy take care of your shoulders (if you dont have the BoA's), helm, gloves, and a shield. Pants are no biggie either on the AH unless you just hold out for the nutty rare ulda pants. Firemane legs are common, and you can also use a green pair to trade 6str for 6stam, yes greens are that good. Boots are just a green unless you want the low armor ones in ulda, which are a guaranteed drop from bosses just inside, easy item to get. If rev is too much of a pain, which i know he can be (avg around 50 runs to get an item in my experience), then crushridge bindings are a common AH alternative. If you are horde your chest piece is a quest reward, so thats easy, if not its a green so thats easy too. Rings are easy AH items. Weapon can be more of a pain depending on what you are goin for. The sword from the same rare in rfd that drops the belt is a great start. If you are alliance the sm quest axe is also killer. Keep in mind that with so much normalization with warrior moves, you dont neccessarily need a super slow weapon like you do with ret palles, depending on spec of course. Your neck piece atleast horde side is a STV quest chain or AH boe.
Again, its really fairly easy to twink a mail melee toon. Boots, if you want mail and not leather, can be a pain and weapon can be a pain depending on your choice. The rest is easy and fairly common.