I agree that with patience, LW is the cheapest profession to level, especially with the input of enchantrix. However, in terms of sheer benefit to a new class, the class relevant skill is best (less so now TBC is mature, but the situation will be reset again in Wrath). My shammies are 4x leatherworker for this very reason, to have a head start in wrath.

Apart from this, engineering and enchanting can both give you a nice boost.