3 races can be a Paladin in Forever: 
Undead on the Horde side, 
Human, 
Dwarf for the Alliance (Blizzard race table). New in Forever: Undead Paladin.
Our picks
Horde
- Undead: The only Horde Paladin, and new in Forever. Cannibalize now restores Mana as well as Health, and Touch of the Grave has a 20% chance to trigger for Paladins.
Alliance
- Dwarf: Artisan's Precision adds 1% hit to spells and attacks, which helps the Judgement taunt land. Stoneform cuts Physical damage. Our tank and Retribution pick.
- Human: Human Spirit gives 10% more Spirit, and Reverence keeps Spirit regeneration going while you cast. Our Holy pick.
These are our opinion, based on Blizzard's beta notes. Blizzard says each race has two active and two passive racials tuned for similar offensive power, so faction, looks and who you play with can still decide it.
What each race gets
- Undead: Will of the Forsaken, Cannibalize, Underwater Breathing, Touch of the Grave.
- Human: Will to Survive, Ruthless, Human Spirit. Blizzard's posts name 3 of the 4.
- Dwarf: Stoneform, Find Treasure, Artisan's Precision, Big Game Hunter.
Sources: Blizzard's development notes and panel recap. Details and what's still unknown are on each race page.
More: race guide · 
Paladin class guide · Paladin leveling guide