I've always felt, out of the playable races currently unable to be Paladins, Night Elves would be easiest to justify. Priestesses of the Moon were already closer in their original depiction to Paladins than the cloth wearing casters in WoW. They wore armor, studied martial techniques and military strategy; they hold prominent positions in the military; heck the Sentinel Army came from them, more or less. Night Elf Paladins need next to no effort to work on the barest level; just swap the bows for melee weapons and you're golden...or preferably silvery blue.
They probably could introduce goblin druids as junk collectors and recyclers to clean up the earth (for a profit)... Junk Dealer (guardian), Salvager (Feral) form would be a rat, Recyclist (balance), Naturalist (Healing) - tree form would be a paper mill.