Since your warrior has blacksmithing covered, which can make many items for your paladin, then how I’d suggest your tradeskills combo is as follows:
1) Warrior – mining and blacksmith. Makes armor and weapons for warrior and pally. Potentially swordsmith.
2) Hunter – My suggestion: skinning and leatherworking. Makes leather and mail armor for himself, as well as armor kits that all your chars can use. If you ever add druid or rogue to your list of characters, they are also covered for gear.
a) Alternative 1: Your own selection of Enchanting and perhaps (gathering skill). Some players don’t like to switch between all the tracking that hunters do normally, and trade skill tracking. I don’t mind it too much. However, consider this before you take up herbs or mining. He also can do skinning and just sell the leather off.
b) Alternative 2: Enchanting and Tailoring – Many people take tailoring with enchanting because you get cloth as drops, not from some special gathering skill. You’ll find use in bags and selling some gear, but ultimately you might prefer to have a cloth class do tailoring for the higher-level recipes.
c) Since you plan to play him a lot, the higher level leather recipes are very nice to have, and many are gained through reputation grinding.
3) Paladin – Enchanter and (gathering skill). I’d almost suggest tailoring because you’ll find use in bags and selling some gear, but ultimately you might prefer to have a cloth class do tailoring for the higher-level recipes.
a) Alternative 1: Blacksmith and take Macecrafting…at least I think that’s what it was called, to make his 2H clubs
b) Alternative 2: Mining/skinning/herbs – some people don’t like switching between Herbs and Ore seeking, so they won’t take those two together, but I don’t mind it too much. Doubling up on mining will be useful because you certainly will need all that ore.
c) You mentioned the paladin may level up slowly. As long as you can get him to level 35, you can do enchanting recipes up to 300. This range provides quite a few good and useful enchants. If you get lvl 51, you can do enchanting all the way up to 375 for various boe recipes that you can get from AH, that don’t require you to be in Outlands gaining reputation to buy the recipes. Your other chars can feed him items to disenchant, even from level 60+ gear.
d) If he’s a disenchanting mule, then I think around level 275 enchanting, you should be good for lvl 63 items or less. So it still requires getting to level 35. But with your characters feeding him mats, money, and items to disenchant, he could conceivably reach 350+ or higher in enchanting without leveling up as quickly as the other two chars.
If you don’t have a tailor, then all the cloth you pick up will be profitable to you. But if you add tailoring, then you may find it hard to generate cash, because your leather, ore, and cloth will all be used. Though maybe the disenchanting mule will cover that part just fine.