Murder was very much a capital crime: Icelandic sagas are typically all about grand vendettas were there is one death upon another. However, there were honorable and not honorable killings, different rules for settling feuds by paying reparations, etc, which makes it a complicated mess. The main rule was, however, that if you killed someone, that person's nearest male relative was responsible for settling the score, one way or another (one exception was if someone left a daughter as sole heir: then she could seek right for herself, exactly as Skadi did after the death of her father).
But even this had one important exception: you could not seek revenge within your own family. Part of the backstory of Beowulf is how king Hrethel had two sons, Herebeald and Hæthcyn, until Hæthcyn killed his older brother in an hunting accident. Since it was not possible for Hrethel to take revenge, he eventually died from grief and shame.
This is also reflected in the story of Balder: His father Odin could not take revenge on Höðr directly, so he fathered Váli to do it for him.
Similarly, Loki was, at least according to Lokasenna, Odin's blood-brother. It certainly seems likely that this would afford him similar protection. This is further evidenced that when the gods finally want to tie Loki with the entrails of his son, Narfi, they transformed his other son Váli into a wolf to do it. The name seems to be of significance: it seems unlikely that two different persons bearing the same name were used in a similar manner for punishment, so there are likely deeper similarities.
The answer is thus that the gods likely wanted to punish Loki, but either hadn't figured out how without impugning their own honor, or that he had already fled when they found out what had happened. Loki then appeared under sanctuary in Aegirs halls in Lokasenna, but were finally caught. Even then, they could not kill him outright, so they deviced another punishment which would leave him alive.
The analysis above is partially based on Margaret Clunies Ross' Prolonged echoes, which discusses Odin and his revenge-by-proxy on Höðr, but which does not discuss the (initial lack of) punishment of Loki, from what I remember.