Ned Coates didn't die (at least in the altered timeline).
He was still alive a moment before Vimes was sent back to the present. We don't see him die, so he might still be alive.
- It's also possible that he died in the original timeline (hence the grave with his name on it), but not the altered one. To avoid a paradox, the History Monks sent him to Fourecks, which had a messed up timeline anyway.
- Would that make him the "Tinhead Ned" who'd occupied the jail cell before Rincewind?
Carcer is still alive.
Think about it. He was sentenced to hanging. Now let's see, which other characters were sentenced to hanging? There was 1) Rincewind, in The Last Continent. Escaped and saved the country. 2) Moist von Lipwig, in Going Postal. The hanging is faked by Vetinari, because he is useful, and he ends up as head of multiple large business organizations. 3) (I'm not completely sure about this one) Owlswick Jenkins, in Making Money. Is rescued and then secreted away by Vetinari, presumably to make something artistic that is very necessary, somehow. Now, who else has gotten the angel treatment? Moist von Lipwig, the incredible thief. Reacher Gilt, expert swindler and crooked business man. Owlswick Jenkins, stamp forger. So Vetinari only does it for normal thieves, not murderers, right? But doesn't it say, in the book, the whole "Would you let a murderer go for a thousand dollars?" passage? It's the same thing. What are Carcer's skills? Firstly, he's charismatic. He is said to almost be able to convince you that he is innocent. Secondly, he's super-sane. That's more or less the whole point. Why the hell wouldn't Vetinari take him? Remember, Vetinari is compared to a little old lady who collects pieces of string, because they might be useful. Every time throughout the book he comes up, he counsels towards the perfect arrest. In the second scene, he asks that shouldn't Carcer be taken in by the book, and says "and ask questions later." He knows Vimes perfectly. He knows that Vimes just wants to kill Carcer. He is subliminally convincing hhim not to kill him. In the graveyard scene, there are three hints. One, on the same note, he congratulates him on a perfect arrest. Two, there is the "What could I prove? And to what end would I prove it?" He is telling Vimes not to pursue this line of inquiry anymore. Vimes's life as Keel is over, and Carcer's life as Carcer is over. Thirdly, "The Job they had to do." Vetinari needs Carcer for something, and he will make him do it. I don't yet know what it is, but I feel like he will come up again. We never see him die. All we see is that he is sent to the gallows... and disappears.
- Except that sparing a cop-killer who'd threatened his family is probably the one thing Vetinari could do that would make Sam Vimes turn against him. He's not going to waste an invaluable asset like Vimes just to acquire the services of an unsteerable psychopath.
- Agreed, Moist, Jenkins, Leonard, et all are kept alive because Vetinari knows the buttons to push to keep them under control. Carcer doesn't have those buttons, like The Joker he just wants to watch the world burn. He's the sort of person that when sent on a mission to kill Colonel Condiment, would take time out to stomp on kids tea-party, slice the throat of of someone who looked at him funny, and then burn down a water-balloon factory all on the way. And not understand what he did wrong, or even there was a difference between any of those acts. Vetinari would have no use for such a man.