I think if you are wanting to be a hardcore raider and raid long term the pserver experience may be worth it to ensure you pick a class you can enjoy over such a long term commitment, but you definitely don't need to do that to just play the game or to be prepared to do well as a healer.
Healing is not difficult to learn in vanilla and you will do fine picking it up as you go.
I think you're better off waiting. Healing isn't that big a deal and you can learn on the fly in the first dungeon you run. I'd worry about getting too familiar with the first 20 levels and making it super boring when you play it through for real.
I'll also say you're better off waiting. You'll learn a lot from running level appropriate dungeons. If you're really keen on playing on a private server though just to check stuff out, go for it! If anything, get used to the lay of the land, the reduced quantity of FP's, etc. If you didn't play vanilla, Classic can be a bit of a culture shock.
Sorry to necro the hell out of this thread...
I wanted to provide my opinion because everyone seems to be saying wait.
And yes, I would definitely recommend waiting as well IF you were planning on practicing leveling paths or level progression. Leveling is a massive part of the game and should be enjoyed, not rushed through. But that's just my opinion.
In terms of end game though my advice is to experiment.
I was torn between paladin and druid because those are my favourite classes. I completely forgot what a paladin feels like to play at end game in vanilla and when I tried one on Retro WoW I can honestly say I am so glad I did that, because if I leveled to 60 and had to play a paladin, I would have felt like I wasted my time. This is just me though and I'm not trying to sway you into not playing a paladin. Play what you want and be the best damned paladin that ever smote the undead!
I levelled to 40 as a Paladin healer on a private server when the Classic Beta began - it was good practice and strongly reinforced my decision to play that class and role on launch. Way MORE fun than I remembered it being in vanilla.
Just be careful not to burn out before classic drops.
You can learn this along the way or even at lvl 60, it isn't that much of a rocket science, however you probably won't hit max lvl unless it's a boosted server.
I wouldn't recommend.
I played on a private server a few months ago to choose my class for sure and tonight I'm going to play for a short while to see how long it takes to get 10s to get a guild charter and 30 tailoring just so I can time it from a fresh char so I know how long I would have to stay up (eu release is midnight)