I have played (and currently am), a warband with no Henchmen, my Possessed.
They started out as failerues the first two battles, but after a couple of Underdog games I got some levels and I started to kick in.
I've been lucky with getting high Toughness, plenty of Wounds, Dodge and all kind of deadly stuff, both my mutants and my Magister has become Possessed by Daemons as well!
For about 8 weeks I've played my Possessed with only the Magister and my two Possessed, and added the mutants lately. After they became Possessed I had to get one henchman though, but for a short while.
I got a magical artifact the other day (the quite deadly dagger), and since none of my possessed or possessed mutants and magister can carry any weapons other than daemonic weapons i had to try to get myself someone with 'that lad got talent', which I managed to on his first level, so now I have a Beastman with the deadly knife and 6 heroes in total in my Warband.