Stone (2002) by Adam Roberts.

The plot summary matches your description:
- Murder convict imprisoned within the plasma of a sun.
- Society where murder is rare.
- Convict is broken out of prison, implanted with an AI, and sent on on mission to kill.
Ae has been imprisoned for a crime rarely committed in the society he lives in: murder (mainly due to the difficulty of killing a body protected by nano-tech). He is placed in a high-tech prison (a stone with an artificial environment inside held in the plasma of a sun). He is "executed" by having his Dot-tech purged from his body, which, while not immediately lethal, will eventually cause him to die of natural causes.
He is broken out and picked up by a sub-light ship, where he recuperates before traveling onward, employed by a mysterious agency. During the escape, he is implanted with an artificial intelligence who relays his instructions. The AI reveals that Ae is to kill an entire planet, but does not explain who has ordered the murder, nor their motive for doing so. All Ae is told is that the nature of his mission will be revealed upon its completion.
And there's a scene where the killer (a woman) cuts another woman's head off, and subsequently buries it, with the severed head being kept alive by nanotechnology:
I hacked and sawed through most of the neck, but the plasticky resilience of the gullet was tough to cut through. I started to lose my self-possession, shrieking and sobbing to myself. The dumb flesh seemed to be resisting me. It was as if the whole universe were taunting me. With several huge blows, one or two of which seemed to go astray, I finally cut the head free from the body.
The dotTech had done a clever thing. This is how smart it is, the nanotechnology: it had realised that the head was severed from the body and it had closed down the blood and lymph vessels to preserve the precious blood in Enkida's brains where it would keep her alive, feeding a small quantity of oxygen to it that the machines themselves absorbed through the skin. But of course it would not be able to keep her alive indefinitely, separated from her body as she was now.
Then I finally climbed out, and went over to the head. I tried to steel myself to pick it up again, but in the end I couldn't. Perhaps I am a coward. I used my foot, and started nudging the head towards the hole, as if I were playing a game of football. I was expecting it to say something, but it was silent, Finally I toppled it over the lip of the hole and in it fell, face down. Then, quickly, quickly, I kicked dirt in after it, over it, covering it and hiding it away. Burying and hiding it away.
You can read a preview of the book here.