When we think of crime and punishment, we automatically think of a powerful central and secular government with (relatively) clear laws handing down judicial sanctions - usually of imprisonment or financial penalties but increasingly including home detention, community service, or restitution to the victim.
This is all the product of post-enlightenment thinking and would be largely unrecognisable (and stupid) to our ancestors. We don't think as they did, and we struggle to get into their mindset.
This cuts both ways - we are equally horrified by the Roman collective punishment of decimation as we are by the fact that a Germanic murderer merely needed to pay a weregild, the price of which was determined by the social rank of the victim - with a discount for Welshmen in Anglo-Saxon law.
Categories of Punishment
All punishments fall into one or more broad categories listed here in decreasing order of severity according to the Western tradition.
Because we are a largely secular society, we don't think of this as being a punishment for crime; but there was no distinction between sin and crime in the past.
The beauty of this system is that no crime goes undetected or unpunished. Whether you get your punishment in Purgatory, in front of the Assessors of Maat, in Gehinnom, or Mictlān, everybody gets what they deserve.
This was not just a matter between a person and god - religion was culture, culture was religion, and both were the law. For your crimes, the priesthood could make things worse in the afterlife; or for your piety, they could make things better.
In the Christian tradition, we have excommunication, which cuts you off from social life (a form of ostracisation) but also put your soul in peril - if you died in this state, you went straight to hell, no passing Purgatory, no collecting $200. This could be a collective punishment, called an interdict, where the clergy would be prohibited from performing those rituals required to make one right with God, such as christenings, marriages, and the last rites.
We also have Hell as the punishment for an unrepented mortal sin, most often suicide, but also unrepentant capital felons, where the Church would not perform a burial.
In the same vein, post-mortem dismemberment, such as being hung, drawn and quartered, which, in a Christian tradition that looked to the literal resurrection of the body, meant that you could never be resurrected. Apparently, a God that created the Universe couldn't stick people back together. This belief faded in the wake of the Great War when the widespread use of artillery meant there were hundreds of thousands of Christian dead in bits so small that not only couldn't God stick them together again, they couldn't be identified.
A time-honoured staple for anything from murder, treason, and drug trafficking to worshipping in the wrong way or, in some parts of the world, being the wrong race in the presence of a police officer.
Just about any way you can imagine of deliberately ending a person's life has, at some time and place, been a method of execution.
Modern usage has tended towards the elimination of suffering, which gave us lethal injection, firing squad, the electric chair, long-drop hanging, the guillotine, and, in the more advanced parts of the world, the elimination of the death penalty altogether. Historical methods tended to include torture, prolongation, and humiliation as a deliberate part of the execution "such as the breaking wheel, keelhauling, sawing, hanging, drawing, and quartering, burning at the stake, flaying, slow slicing, boiling alive, impalement, mazzatello, blowing from a gun, schwedentrunk, and scaphism. Other methods which appear only in legend include the blood eagle and brazen bull." And, of course, crucifixion.
This can be direct punishment of the perpetrator or, for collective crimes, execution through drawing lots or decimation.
Human sacrifice is generally not execution as it was usually not a punishment for a crime but a great honour for the sacrifice - even if the methods came from the same playbook.
This includes one-for-one maiming, the most famous being Exodus 21:23–27 "If men strive, and hurt a woman with child, so that her fruit depart from her, and yet no mischief follow: he shall be surely punished, according as the woman's husband will lay upon him; and he shall pay as the judges determine. And if any mischief follow, then thou shalt give life for life, eye for eye, tooth for tooth, hand for hand, foot for foot." However, this was also a feature of Babylonian, Greek, Roman, and Islamic law.
It also includes removing the hands of thieves, the genitals of adulterers, and the tongues of blasphemers. Blinding was also a common punishment, often politically driven, because, throughout many parts of the world, a blind person could not inherit.
It also includes branding, scarification, tattooing, or mutilation of the ears or nose, but this is primarily intended as ostracisation to mark the criminal permanently (see ostracisation and humiliation below).
Depending on the technique, mutilation may effectively be capital punishment. Also, some forms of corporal punishment, like flagellation and caning, may permanently scar their victim, although that is not their primary purpose.
Humans are social creatures, and exclusion from or falling in standing in society is particularly devastating - particularly in a pre-modern society when ostracisation often meant death.
Excommunication has already been mentioned. We also have being declared an outlaw - this wasn't, as it largely is now, a synonym for criminal - it was placing someone beyond the protection of the law, effectively making them fair game for anything anyone felt like doing to them. Exile or banishment was another punishment usually reserved for those of high standing, like nobles or royalty.
Forcing people to be publicly exposed and subject to verbal and physical abuse, such as through the stocks or pillory, was common. Having convicted people bear a mark of shame or a visible mark of their crime (see mutilation above) was also common.
Arguably, maintaining criminal records and sex offender registers is a form of humiliation, particularly if it is made public.
From slavery, to penal servitude, to indentured service, to transportation, to modern prison workshops, if you can make someone pay for their own punishment, people will find a way to do it.
However, imprisonment per see has only been considered a punishment since early modern times and came in with such strange notions as reform (hence reformatory school) and penitence (hence penitentiary). Before then, a prison was a place where you kept people while awaiting trial or punishment - or people who were just too damn dangerous to be let loose.
Caning, whipping, hitting with sticks, hitting with nettles, breaking bones, holding people in painful positions, hitting with the hand, etc.
These have all been (and some still are) judicial punishments as well as methods of maintaining discipline in children and military forces.
These are basically two types: fines paid to the government, or restitution paid to the victim or victim's family.