Instead of punishing with death, how about preventative measures? (Along with a nice period of time in jail or prison) Example:

Rape: scissors + ... = eunuch

This would likely deter many rapists, and would prevent others from ever doing it again. Very effective.

Not all crimes will be dealt with this severe of a penalty, of course. A petty thief will not need his hands chopped off, that's a bit extreme. For crimes that are more severe or more socially unacceptable, punishments like this could be very effective without making death the first option.

On another matter, which is actually crueler: letting a person rot in prison their whole life or killing them? If they're really bad, they may be locked up in their own private cell, not much larger than a bathroom, no windows, measly amounts of poor quality food, nothing to do but to sit there with only themselves for company, waiting for the day they will die, either naturally or otherwise. There's not much of a difference, except that one way they take longer to die, so which is really more humane?