Turtle WoW

It's my first time leveling a paladin in hardcore and I would like to know the safest build to do it.

I was thinking of doing it as Retribution, but I have also seen that Protection is a viable spec, due to the changes that Turtle WoW adds, and now I'm a little confused. All help is welcome

I'm not sure of the specifics, but ret is usually the way to go until mid 30s when aoe farming as prot becomes easier and more efficient. That's just a big generalization though, so you'd best root through the paladin forums, guides and discussions if you want specifics.