Hello everyone,
This could seem like a pointless guide - just explore and skin and you will eventually level it up, right? Well, it's good to save some time.
I did this as a 73 lvl Death Knight (with flight paths unlocked because of class) with 100% ground mount, no flying.

Time: 69 min (I have not speedran this, it could be way faster.)
Note: If done with 80 it will be faster. If done with Pala (Crusader aura) it will be faster. If done with flying - it will be faster. You get my point.

Spots to skin:
1. In front of Orgrimmar until level 11 mobs are green (50-55 skill).
2. Go back to Orgrimmar and train Journeyman skill.
3. Go to Crossroads and start going South, skinning everything in the way.
Note: Once a certain level turns green, stop skinning them and move downwards to find higher level mobs.
4. Skin level 21-22 mobs east of Camp Taurajo until 125 skill train Expert skill in the camp.
5. Continue towards Thousand Needles and get around 160 skill before you enter. There, level 27 mobs will turn green at 185 skill. Continue towards Tanaris and skin until 225.
6. Go to Camp Mojahe, Feralas, train Professional Artisan and start skinning level 40-41 bears and wolfs and moving up the zone. Skin until 300.
7. Go to Shattrath and train Skinning Master. Fly to Hellfire and start skinning around Zeth'Gor while moving to Terokkar Forest. Once 350-360 go back to Shattrath for training.
8. Go to Garadar, Nagrand and skin west of the lake next to the village until 375 (can get up to 400 in this spot with Talbuks).
9. Go to Northrend.

If you level up to 400 in Outland you can go as high as Zul'Drak in Northrend - level 76 mobs.