I really would not try to add any fish other than Africans. Most likely they will not make it. Any fish you add to the tank will need to be as aggressive as the African.
"I'm not going to overstock it, that's just cruel !!!"
Actually, when it comes to African cichlids, especially Mbuna UNDER stocking is more cruel. The reason why is because with less fish, the least aggressive ones get picked on VERY badly! When you over stock the aggression is spread out so one or two fish do not get the brunt of it. That is why all the stuff about Africans say to over stock. How many fish do you have right now? If you have too few that is probably why you have such issues with adding to the tank. The territories do not overlap and even rearranging does not help. I have had the best luck with adding smaller ones than the ones in the tank. My adults do not see the smaller juveniles as a threat and leave them be.