I could easily see people in lawless lands, or seeking order at any cost to devote themselves to Hextor or Bane.
I've seen enough real people in my life embrace fundamentalism, ultra nationalism, and fascism to know one doesnt have to be a 'bloodthirsty psychopath' to embrace the teachings of deities like Bane and Hextor.
Deities like Cyric would promote the religion as freeing oneself from social norms and the shackles of morality, and doing or taking what you want, when you want it.
This would also appeal to a lot of people who are not necessarily bloodthirsty psychopaths.
A lot of normal people would baulk at the level of restraint, honor, self sacrifice, altruism and mercy that the Good deities demand.