At level 12, a Paladin gains a quest from his skill trainer (IF if a Dwarf, SW if a Human) to learn the resurrection skill called Redemption.
Unfortunately, if one waits to long to get the quest it is no longer there. For me, it was level 20 when I went to go check.
Some instances I have heard of players going back as soon as Level 15 to grab the quest only to find it not their either.
To confirm, I have checked the following NPCs just to make sure none of them have the quest for me.
- Paladin Trainers in Ironforge
- Jaina whatever her name is in Ironforge
- Paladin Trainers in Stormwind
- The dude who gives you the Tome quest in Stormwind (SW Keep)
- Kharanos Paladin Trainer
- Goldshire Paladin Trainer
None of the above have the quest for me.