John Constantine (of the comics) is far too amoral to be a Paladin. His mortal allies end up dead or damned or both. (I didn't watch the movie...as soon as I saw they cast Keanu, I knew I couldn't watch a 30 something brunette American actor play a role of a 40 something blond Cockney urban wizard...especially one who was overtly based on the physical appearance of Gordon Sumner aka Sting...who is among other things, also an actor.)
At one point, he had sold his soul to not just one, but SEVERAL devils...hardly the stuff of Paladinhood.
His powers do not appear to be innate, but rather the product of learning, so Sorcery isn't quite it. He seems more a Specialist mage than anything else (as far as casting goes)- probably an Enchanter, dropping the Evocation and Transmutation schools. I know those are powerful spells to give up, but in my years of reading the character (back to his intro in Swamp Thing), I've not witnessed anything resembling the overt power of those 2 schools in his use, but I have witnessed protection spells, conjurations, illusions and divinations.
Still, it has been hinted that his ancestry is a little demonic, so perhaps a mix of Sorc and Specialist would be appropriate. The superior choice, IMHO, is to make him a Tiefling (Planetouched, MM p209). While it is a +1LA, it gives bonuses to skills essential to the character, maintains the demonic bloodline, and still makes his magery the product of learning rather than blood.
He DEFINITELY has some levels of Rogue or Bard. He's smart, and he's quite the con artist. Your choice.
Given his brand of arcane judo, you might even use some levels of Spellthief in there as well.
As a recent issue of Hellblazer revealed, his primary gift is to be convincing. The first victim of his "occult" powers was a bully whom JC scared into getting himself seriously injured with secret facts about himself...secrets he actually learned from the bully's equally bullied younger sister bent on revenge.
He's even convinced otherworldly beings that he's more powerful than he really is...at least at that moment in time.
So...he's going to be high on both Int and Cha...with lots of points spent in Bluff, Gather Information, and Intimidate.
