Our society, today, think it unjustifiable, and this echoes in most of the answers presented here. I find those answers helpful in identifying the "problems" to solve, but disappointing in stopping at those problems.
What are the impediments?
Firstly, as mentioned, murders are unacceptable because they are by definition unacceptable. I side with @hszmv and will therefore use killing rather than murder. A killing is the act of killing someone intentionally^1 , whether lawful or not. An unlawful killing is a murder.
There are many instances of sanctioned killings today or in our past. The death penalty, soldiers killing other soldiers, policemen killing criminals, are all examples of such now. In the past, we also had duels to the death, owners killing slaves, etc...
Hence, there's definitely room for maneuver here.
Secondly, there's the problem of acceptance, and specifically of the just-killed person's friends and family accepting their death. Without acceptance comes retribution and an endless cycle of violence, or at least dreams of such if the power disparity is great.
In the above examples, whilst most killings are sanctioned by the society, the family or friends of the people killed mostly do not accept their death. There is one exception: duels of honor. When gentlemen dueled, and one died, whether by accident (in a duel to first blood) or by design (in a duel to death), the family of the deceased accepted their death to some extent. They were unlikely to ever be friendly again with the other party, but they were also unlikely to seek retribution.
The key here is to find a virtue that is more valuable than life.
In duels of honor, that virtue is honor. Living dishonorably would bring shame to the person, and by extension their family and friends, hence they would duel, and either prove their honor, or cleanse it, somehow, with their death.
Thirdly, there's frequency. If everybody keeps shooting everyone, population dwindles until noone's left. For a society to survive, you need population to at least maintain itself, meaning that in average an individual should kill strictly less than half the number of children they had and who died of natural/accidental causes well into adulthood.
Assuming a modern society, with few deaths from natural/accidental causes, it's essentially half the number of children they had minus one. So a couple with two children cannot kill anyone, while a couple with three can kill one other person (but not one each). One other person, in their entire lifetime. More children, more leeway.
^1 The technical term homicide covers both intentional and unintentional killings, so in terms of scope all murders are killings, all killings are homicides, but not the other way around.
Intermezzo
Having a specific cast (warrior, priests, nobles) have the right to kill indiscriminately a specific cast (other warriors, pariahs, lessers) is arguably easier, but where is the fun in easy?
What kind of society would that be?
Or why would anyone accept the death of their beloved?
Several potential ideas:
- A society idolizing Luck, for example. Those who get shot at random are unlucky, and would have brought their unluck onto their family and friends. It's better that way.
- A society idolizing Honor. In this case, rather than "random" shooting, I would rather see "random" dueling.
- A society idolizing Death. This world is a purgatory, those who die young are the lucky ones, freed from their burdens! (But those who commit suicide are cowards, doomed to hell)
- A society idolizing Parsimony; I'll detail it below.
The most difficult thing, in any of the above, is really the frequency aspect. Why would a person who has lived a peaceful life for 30 years kill one other, then live peacefully for another 40 years until their death? It could be justified for an individual, but it seems hard to justify that every person would behave so, with a "sprinkling" of one/two killings in their life.
And thus I submit a society either overly conscious of its impact of the environment, or living with strictly finite resources. The number of individuals in the society is capped by law for each district. Yet, at the same time, nobody could agree on criteria to cull the excess: killing the old means losing wisdom, killing a certain group is discrimination, ... and thus it was decided to leave it to a mixture of fate and common sense.
Every week, in every district, a lottery takes place, designating a number of random adults -- based on excess -- for the culling. They are given a one-time license to kill. Some will choose to kill themselves, others will take the opportunity to kill a person they loathe, most find it easier to kill a stranger they never heard of, and whose family and friends they won't have the suffer the grief of. Motives are not questioned by authorities, only timeliness. They must be done before the next round of lottery.
It's hard to lose a friend, or a family member, to the culling. But it's necessary, lest we run out of resources and every body dies. So someone has to die. And it's frankly egoistically shameful to begrudge the death of your friend and wish it had been someone else.
It's all for the greater good.