In my opinion Kahliel is a super fun hero. I love those heroes who are the heads of their archetypes. For example, Radagast and creatures, Saruman and doomed, Hirluin the Fair and outlands, etc. While his ability isn't great as there isn't a ton of Harad allies, it can still be game changing (hopefully when/if fantasy flight makes more expansions, Harad is a trait they might come back to).
Who he works with:
Denethor to get Steward of Gondor out on him early.
The Storm Comes to have help with paying for the big allies.
Elrond and Vilya could help bring in some of the harad allies.
Errand-rider to transfer spare resources over to him.
Of course:
My opinion:
Fun Factor: 9/10
As a hero: 6/10