Bloodstorm Paladin Edit
A fairly powerful build (at least for my mileage) that has some trouble surviving 'til it gets what it needs but kicks the game over afterwards. It mostly takes advantage of the Bloodthrust ability, being that it costs no MP, always hits and does damage based on your current/max HP.
So basically, put everything into VIT and the HP-boosting talent. Yes, everything. Weapon choice is not terribly important to the build, so use best judgement based on your current gear.
What you need is a reliable source of inflicting the bleed status on yourself; Sacrifice is risky, and you need another way to heal aside from 4-heals (since that removes bleed). An Unstable weapon (or foe), or a Seeker weapon work great.
Top priority on gear, aside from bleed sourcing, is VIT. Even defense and block chance can be ignored for high VIT! After that, INT for better healing is useful.
But why a Paladin? After all you could do this with any class right? Simple - dang near everything you do in combat as a Paladin heals you to some extent. Plus, what is more appropriately emo and edgy than a paladin who stabs people with their own blood?
Kraste + Priest Paladin Edit
There is great synergy between the Paladin class and the Kraste race. The latter receives a nice damage boost from INT (both directly and from the "free" damage that comes from having a large mana pool), plus has a chance to freeze enemies for added survivability. Paladins regenerate health when above 50% MP, regenerate health when spending MP, and receive +1 ATK for each point put in INT while leveling up. So it's very clear that investing in INT gives some nice bonuses for this combination!
It's important to note, however, that the Paladin bonus ATK from INT does not apply to INT gained from items...only INT assigned at level-up. Which is why this build will still depend on some STR.
Attributes from levels: +2 VIT and +2 INT at each level up. VIT keeps us alive, INT gives ATK and MP. Pretty self-explanatory.
Mastery: Mace/maul since they get bonus ATK from both STR and INT. You won't be able to crit, but our DEX is garbage anyway and the mastery itself gives a nice damage boost.
Passives: Focus on the HP-boosting one early on until you reach tier 2 or 3; Try and shoot for around 3k HP as an initial goal. Then switch to raising your other passives to tier 1 with armor > MP > ATK. Then keep armor and HP 1 tier ahead of the others as you continue to level (eg: go for tier 3 HP + armor, then tier 2 MP + ATK).
Gearing: VIT and STR are most important, with INT as a close 3rd. A little WIS is also nice to offset the drain from barrier, but not a priority. Focus on getting Heavy armor (for high damage mitigation) and a Heavy shield (so we aren't hit with a -25% damage penalty) with a high block rate. Try and make sure your weapon is aligned with your faction for the 20% ATK boost. Any item with the "Enraging", "Deflecting", "Frozen", or "Coldheart" properties is extra-useful.
Advancement: Priest. 5% chance to heal on block/dodge/evade is OK since we'll have a decent block chance, but the other bonus is what really shines. Free heals that keep your barrier up are amazing!
Combat: Keep a barrier up at all times (this might be tough when fighting smiters and manathreshers). Between barrier + high block chance + high mitigation + high health + Paladin passive heal from being over 50% MP, you should be able to take big hits and keep smiling. You'll also be able to SHOCK and FREEZE the enemy thanks to Kraste's freeze chance + chance to SHOCK with barrier active, both of which the overall damage you take by reducing the number of incoming enemy attacks. If do you ever run into trouble, just spam heal since the MP is refunded and it keeps your barrier up. Get your rage bar maxed asap for larger passive healing and to unleash our awesomely powerful feral ultimate...but remember that this is secondary to staying alive.
This probably isn't a "perfect build" but its by far the best one that my noobish self has run so far. It has great survivability without sacrificing much (if anything) in the way of damage, and it's pretty easy to play.