A year ago I would have said that Paladin/Reaver, heavy on the Paladin, was loads of fun. Dunno about now though.
As for Justicar it depends on how you want to do it. If you want to do a "sword'n'board" type arrangement that you can also tank 5-mans with you'll probably want to stick with the standbys of Shaman and Druid. If you're interested in just solo work then those same souls can work, but with a heavier focus on Shaman and/or Druid. Likewise some of the more popular builds have involved Justicar/Inquisitor/Shaman or Druid.
Really once you get http://www.rifthead.com/stc/zm0f0vlhM00RcR you can probably mix and match just about anything (except maybe pure healers, and even there it's not necessarily bad, just sub-optimal) into your build and have it work. You're more or less guaranteed infinite mana leaving the only questions of how you'll keep yourself alive and how quickly you want to kill things. --- Stop complaining. I could have done this more painfully. - Dryad from Sacred 2.