Good questions. The answer to your first question is, basically, all of the things you list in your second question, plus some. The justifications for criminal punishment are typically divided (oversimplistically) into two theories: "backward-looking" retribution and "forward-looking" consequentialism. The forward-looking theories (often associated with utilitarian ethics) focus on the future benefits of punishing criminals: (1) deterring the criminal from further crime, (2) deterring others from carrying out crimes, and perhaps also (3) rehabilitating the criminal and (4) restitution of the victims.
The backward-looking theories (often associated with Kantian ethics) focus on what happened in the past--the crime committed, the harm done, the guilt of the criminal--and aim to punish the criminal as much as he or she deserves it, which may include making the criminal suffer an appropriate amount, but perhaps also forcing him or her to make up for the crime with restitution. This justification may be seen as "exacting revenge," but revenge is typically more personal and not necessarily based on a moral justification.
Now, I suspect--and there's evidence to support--that we are motivated to punish criminals and others whom we perceive as doing us (or our loved ones) harm by strong feelings of resentment and indignation, and we feel relieved when we see these transgressors punished, including in significant cases, seeing them suffer or die (consider how people felt about bin Laden's death). These feelings likely evolved in part (and somewhat ironically) to promote social cohesion: Cheaters had to be punished severely to promote cooperation. But this suggests that our retributive impulses, and our feelings of revenge, may largely serve forward-looking goals--promoting social cohesion and preventing future wrong-doing.
But motivation is not the same as justification. The evolution of our legal system includes depersonalizing revenge, preventing the "spiral of revenge" (e.g., family feuds), and tamping down some of our impulses to punish severely and well beyond what people deserve (e.g., to send a message)--the 8th Amendment against cruel and unusual punishment illustrates this goal.
Notice that desert (retributive) theories may sometimes suggest less punishment than deterrent (consequentialist) theories--it may deter better to cut the hands off robbers. On the other hand, consequentialist theories often suggest less severe punishments, since the best future consequences are often served by trying to rehabilitate the criminal (e.g., educating him or her). If the death penalty does not deter (and the evidence suggests it doesn't), then consequentialist theories require getting rid of it. Retributive theories can still allow it, assuming some criminals deserve to be killed (theories of what people deserve open up lots of cans of worms, including whether people have the sort of free will that allows them to deserve punishment).
So, what sort of punishment would lead to the most just society? My own view is that it will include a hybrid justification, recognizing that giving people what they deserve (paying close attention to what capacities for rational control they have), with state-sanctioned (democratically approved) punishment, can play an important role in satisfying our sense of justice (including our deep feelings of retribution), while also serving the purpose of deterrence. But rehabilitation and restitution might best be served by helping those criminals who can be helped and allowing them to pay back their victims and society, rather than locking them up in nasty prisons.
These goals can compete. The "war on drugs" illustrates a conflict between harsh penalties justified by both desert and deterrence and treatments for addiction that would likely have better long-term consequences.
I hope these beginnings of answers to your complicated question are helpful!