I leveled LW and Skinning together so I always had a supply, or could resupply, when needed. Skinning certainly leveled up much faster than the LW itself.
Typically the level of your character is about right for your tradskill level as you can only level a profession so far before you have to level the character again, so you should be close to the zones you need to level up the profession as well as gain experience. If you started LW at level 80 then just use the search feature here or go through the low-level progression zones as if you were leveling for experience - this assumes you can also skin. You won't be able to reliably gather leathers in any useable quanitity unless you can skin as well.
If you're a skinner, then you can search this site, via Items, Search (top left menu or navigation bar or you can enter "thick leather" [without the quotes] in the Search database box in the top right of each page on this site) and enter the item name - it will provide a list of which mobs the item drops off (or can be skinned from). It will also list if it can come from chests, quest rewards, etc. All from information provided by staff and users; sometimes the data is outdated but you usually get a good idea of where to go.
The return for such a search is at the following link:
http://wow.allakhazam.com/db/item.html?source=live;witem=4304 Refer to the Dropped tab (the link defaults to it) - it lists 581, but only shows the top 3, percentage-wise, animals that "drop" the item. Also listed are the zones to go to find animals that will yield the leathers. There are many.
There are comments from people listing their favorite places to farm the leathers as well.
Each return also has a link to wowhead and thottbot to get more info. Lately it appears as though wowhead links are most up-to-date for information, at least for what I've been looking up.
If you're not a skinner, then either pick it up for your second profession or make friends with one, else you'll be at the whims of the market.
As you eluded to, you can also take low lower level leathers and make the next higher ones if you need to in a pinch.
Good luck.
Added:
To power-level LW, I assume you mean level as fast as possible for as cheap as possible...
I leveled up whatever pattern was orange or just-turned yellow (as orange is a pretty much guaranteed skill up, yellow usually is, green often isn't unless it just turned from yellow) that required the fewest items - and only leathers when possible - this prevented having to farm or buy other mats. Be sure to get new patterns as soon as they are avilable as new items often have fewer requirements than older ones that may still be orange or yellow. Also look at what you will be able to make and be sure to keep those items you get while adventuring in case you can't avoid having to use them to level LW. Things like the hides, fangs, spider silks, gems, etc. are often needed. Threads too, but those are bought at the vendors for little cost.
You can also advertise in trade (and guildmates/friends) that you will make stuff for free with their mats - can save a lot of money, if not time.
Edited to actually state what I did to level as the heading states, but the question didn't...
Edited, Feb 16th 2010 6:34pm by Taviras