Since they are all already dead and the entire story takes place in the Afterlife, no character in Angel Beats! can actually be killed permanently- they just return to "life" within a few hours. But suffering enough damage to kill a living person still hurts a lot.
Csezlaw Meyer of Baccano!. He was tortured by another immortal that he had deeply trusted for at least one hundred years under the pretenses of "testing the limits of immortality". Understandably, at his first opportunity he cut his right hand free to devour his torturer (the only way to kill an immortal, performed by placing your right hand on their head and thinking you want to eat). As if that wasn't enough, devouring absorbs memories, so he has memories of doing all that to himself for a century, along with the knowledge that it was done purely out of sadism.
Even after that, it turns out he could still be traumatized further: after he tried to have an entire train car full of innocents killed out of paranoia, Vino decides to dish out some of thatspecial Rail Tracer justice and grind his limbs off on the train tracks until he (Vino) gets bored.
In the manga, Blade of the Immortal, the protagonist Manji is cursed with an infestation of "sacred bloodworms" which close and heal any wounds he suffers— even severed limbs. However, Manji still feels the pain of his injuries, and the series is about his quest to redeem himself for his previous crimes to end the curse.
In Code Geass, C.C suffers several temporary deaths, including (drumroll, please) being crushed to a paste at the bottom of the ocean. Fortunately, it all happened offscreen.
And that's just during the events of the series; Flash Backs to her past reference quite a few horrific deaths in her past, including the iron maiden, guillotine, and burning at the stake, complete with images of her struggling against the ropes and screaming in pain the whole time.
Kore wa Zombie desu ka? has this as an important factor for both the main character and Kyouko. While a zombie, Ayumu can still feel any injury he suffers, his non-Magical Girl power attacks break his body painfully, and he painfully dries out in the sun. Kyouko has stolen dozens of lives and so isn't afraid to die or be horribly maimed in combat, though she does still suffer pain.
Perhaps the most clear example of this was when Ayumu used his chainsaw to kill a downed Kyouko repeatedly while she was incapacitated, complete with constant screams of pain. And she was still alive and terrified afterward.
This comes up in Mnemosyne— the immortal protagonist gets put through a lot of pain and suffering. The tagline for its trailers was "It only hurts forever."
Hidan from Naruto needs to use a fighting style that includes self-mutilation to maintain his immortality. His partner isn't very sympathetic when he specifically comments on how painful decapitation (and being picked up by the hair afterward) is. Then there is the Fate Worse than Death Shikamaru comes up with to deal with his immortality - although supplemental material stated he would eventually die from it. But not before he begins to rot while still conscious.
The Big Bad of Ninja Scroll comes to seriously regret his immortality when he is gutted, covered in molten gold, and dropped to the bottom of the sea.
In YuYu Hakusho, Kurama traps Elder Toguro in a plant which gives its victims visions of their worst fears while slowly draining the life out of them. Unfortunately for Elder Toguro, his regenerative capabilities surpass the draining capabilities of the plant, so he'll forever live his nightmare of being unable to kill Kurama.
In The Sandman, the immortal Hob Gadling once comments on how it feels to starve when you are unable to die. Although when promptly offered the chance to renounce his immortality, he turns it down, as he has so much to live for. Being immortal, he always has the chance to improve his lot (and indeed, the next time he meets his benefactor, he's pulled himself into high society). The whole point of his first story (besides its reflection on Morpheus's character) is to subvert the Hell out of this trope because, for all its suffering, life is worth living and certainly preferable than the alternative. It's a bit weird in a comic where Death is so nice, but it works very nicely, especially with Gadling's later appearances.
Cain and Abel. Abel is the first victim, and so he has to spend eternity reliving his story by having Cain repeatedly murder him on a daily basis, sometimes in rather horrid ways. Cain is the first murderer, and so he has to spend eternity reliving his story by murdering his brother on a daily basis. Their family dynamic is a little disturbed.
Wolverine's near-immortality allowed him through the years to survive many things that would make a normal man beg for death, including multiple injections of molten metal into his bones.
In Fables, Goldilocks is immortal as long as she remains a popular character. It leads to a tragicomic scene where she takes an axe to the head, gets shot, hit by a truck, thrown off the cliff into the river and nibbled on by the fish all the way to the sea (which took over a week of constant drowning and returning to life).
Lucifer has a single issue detailing an immortal woman who was cursed with eternal life in Phoenician times for disrespect to the gods. Part of that curse is that her body basically repeats what it was doing when she was cursed, day after day— and she miscarried a few hours before she was cursed.
In Phil Foglio's adaptation of Myth Adventures, the villain Isstvan has suffered through this for (presumably) centuries. The whole plot is set in motion because he's trying to get himself killed. In a bit of a subversion, it's hinted he was crazy even before all this happened to him.
Probably what Jhiaxus feels in the IDW Transformers continuity, as it means that bitter former guinea pig Arcee can torture him indefinitely.
The biggest downside of the immortality that Vandal Savage possesses is that it prevents him from removing the agonizing intestinal cancer he was suffering from at the time he became immortal. He won't die from it, being immortal, but his life is one of constant pain.
Marvel's Mister Immortal's power has him instantly return from the dead whenever he dies, in perfect health. However, the pain of dying often leaves him in an Unstoppable Rage that he uses to defeat his opponents.
The angels in Weightless, and how. First off, they're kept as sex slaves and ridiculously dehumanized; secondly, they have an incredibleHealing Factor, meaning that people can do whatever they want to an angel without having to worry about damaging it permanently and often torture them for fun, and they can't even kill themselves to escape it.
Xander uses this to talk down Shepard in The Zeppo Effect after she discovers his immortality when he electrocutes himself so the team could escape a Death Trap. Not only is death still incredibly painful but knowing that it isn't permanent doesn't make it any less terrifying for him or Buffy and Willow.
Death Becomes Her: Goldie Hawn and Meryl Streep become immortal, but they can still be injured (though it doesn't hurt). They beat each other up a lot. At the end of the film, they're both shattered to pieces but still alive, as the immortality method does nothing about preserving the physical body, just prevent their souls from leaving it.
Highlander contains a scene set sometime during the 17th century in which Connor McLeod shows up to fight a duel while stinking drunk. His opponent swiftly runs him through to no effect, since Connor is both immortal and too drunk to pretend otherwise, (this was before the idea of temporary death, which only was shown in the TV series) and simply gets right back up. A montage of Connor getting run through repeatedly ensues, until finally, still drunk, Connor apologizes for his behavior towards his opponent's wife and wanders off none the worse for wear. The other guy's face is priceless.
In Men In Black, the character Jack Jeebs has a Healing Factor so powerful he can survive even if the Chunky Salsa Rule is invoked! Though as he remarks after K quite literally blew his head off, "Don't you have any idea how much that stings!?" Oh yeah, it sucks to be Jeebs.
Jeebs: Oh great, right in the piehole! Now nothing's gonna taste right.
Jeebs looks a little worse for wear in the second film, though. Word of God is that not all parts grow back the same. In the animated series, Jeebs's brother shows up at one point and reveals that, in his family, blasting each other pretty much means "Hello", although it's usually Jeebs who gets blasted.
Ernie: Eating brains... How does that make you feel?
Zombie: It makes the pain go away!
In the first Wishmaster film, the heroine wishes for the evil djinn to blow his own brains out. He promptly pulls out a revolver and does so. The Djinn quickly heals from this and informs her that he's immortal but adds that it "hurt like hell!"
Inverted in The Wolverine. When he was immortal, Wolverine's wounds healed quicker and so the pain faded faster. When he loses his healing factor, the wounds and their pain linger.
In the opening of the first Blade movie, Blade dispatches Deacon Frost's Dragon Quinn, a vampire who can heal from most injuries. Blade notes that he's run into the guy so many times by that point that he's getting bored with hacking him up all the time, and tries burning him to a crisp instead—which still doesn't hold. Later, Frost himself messes with Quinn as well by pretending that he's gonna chop off his arms again, then stops at the last second.
In the Belgariad, the gods have no Healing Factor because, being invulnerable, they have no need for it. When Torak finds out the hard way they aren't invulnerable to things more powerful than themselves, he spends the rest of his life in terrible agony from the resulting burn. The immortal archmage Zedar is condemned to eternity sealed in solid rock.
The titular artifact of The Legends of Ethshar novel The Misenchanted Sword grants its owner eternal life so long as they retain their ownership. However, this portion of the magic has two staggering flaws that the first, and so far only, wielder discovered. First, it doesn't prevent the wielder from aging, and will in fact prevent a natural death. Second, it will only prevent the wielder from dying. It is perfectly alright with letting them be maimed, blinded, or any number of other horrible things that happen when one wields a bloodthirsty sword.
In the Incarnations of Immortality series first novel "On a Pale Horse", if Death does not collect an assigned soul at its time, the person cannot die. But they remain in agony until their soul is taken. His first client had her neck broken from a shard of glass, but was in intense pain until Death took her soul from her body.
Death can also partially pull a soul out of anyone has an attack. He can do this to another Incarnation, but their nature anchors the soul to prevent it form getting completely pulled out. In both cases, it is excruciating.
Apeshit takes this about as far as it can go. Immortality means surviving everything from splattered brains to being sodomized with a kitchen knife.
In J. R. R. Tolkien's Middle Earth, not only do Elves not die of old age (though to be fair they don't really age either), but their bodies can only be destroyed by the most extreme sorts of injuries. This makes torturing an Elf particularly "fun." One Elf, Maedhros, was taken captive by Morgoth and hung by the wrist of his right hand on a cliff face for decades until he had gone quite suicidal.
In the short story "Gilgamesh in the Outback", when people die, they end up in Hell. Now, in this story, Hell isn't really a bad place. You can eat normal food (but have a real hard time passing it) and can have sex (but no orgasm). And, when you die, the Undertaker fixes you up and returns you eventually...but you feel ALL of the pain involved in your death. Get shot, and you feel the pain until you die and remember it when you come back.
In the Magic: The Gathering book The Thran a planeswalker (read:god) is betrayed and captured. They can instantly regenerate any injury, and teleport across dimensions at will. So a drill is inserted into her head, constantly scrambling her brain to prevent her from teleporting, while the Phyrexians vivisect her.
Note that these are Classic Planeswalkers, pre-Mending. New-Planeswalkers aren't immortal.
Casca: The Eternal Mercenary has this built right in. Casca can't die, or even be maimed, until Jesus comes back. Thus, he manages to survive many deaths over the course of the series, up to and including drowning and reviving uncountable times in an underground river and having his beating heart cut out of his chest in a ritual sacrifice.
In Vulkan Lives, Vulkan is revealed to be immortal, capable of regenerating from anything that can kill him. The Night Haunter tests the limits of his immortality very thoroughly.
The vampires from The Vampire Chronicles can heal from just about anything, given time, blood, and the right replacement parts. However, if they're limited to human blood, rather than the medicinally more potent blood of other, ancient vampires, healing from severe wounds can take years, and they feel pain as acutely as humans.
The immortality of Jack Harkness in Doctor Who and Torchwood. He dies, then simply comes back to life a short while later. Some of his enemies really enjoy killing him, in which case this ends up happening every few minutes or so.
In "Children of Earth", we get to see him come back from being blown to smithereens — and it's not pleasant. His body literally grows back layer by layer, and he regains consciousness as soon as his organs are working, but before his skin is fully done healing. He does a lot of screaming that season.
In "Miracle Day", all humans get to experience this. Hence the profits of PhiCorps skyrocketing when their highly-effective painkillers begin selling like hotcakes.
The Doctor revealed in a Wham Line in the transition from his Tenth to Eleventh form that changing from one Doctor to another hurts, and the pain is infinite — and that the Doctor really is dying. A whole host of Fridge Horror there. note On the other hand, there's quite a bit of Depending on the Writer here. No other Regeneration has ever been treated half as dramatically as the Ten-Eleven shift.
While Time Lords have absurdly long lives, they note in the original series that they consider true immortality to be a curse, so much so that they use it as a punishment at one point.
There was an episode where a guy made made a Deal with the Devil to live forever. Getting bored with life over the decades, he eventually amused himself by committing crimes. When he was finally caught and arrested, he got a life sentence. He then pleaded with the devil to die, and the devil granted his wish.
In the 2002 revival, the Angel of Death decided to slack off from his job for a day, which had some Unfortunate Implications for some firefighters arriving at a hospital, burnt to a crisp but still alive.
In True Blood, the vampires' bodies regenerate when they're injured. While this is generally a pretty good thing, it can have repercussions.
Jessica discovers a nasty side effect of regeneration. She's a virgin when she gets turned, has sex for the first time in her vampire form, and then discovers that her hymen grows back. After each time. Forever.note In later episodes, Jessica's constant virginity is never mentioned. She's shown to be enjoying sex very much. Apparently, she's gotten used to the pain.
Russell Edgington experiences the punishment kind; buried alive in concrete while tied up in silver (silver immobilizes vampires and hurts them badly). Also in Bill's trial we learn that the punishment for killing another vampire is to be buried alive in a silver coffin for years.
In the episode "The Zeppo", Xander gets undead sociopath Jack to back down and deactivate his bomb in the school basement by pointing out how immortality won't be any fun when he's blown to bits. The story thankfully didn't dwell on the aspect of Jack and his undead pals being decapitated, crushed, or eaten.
Affable villain Mayor Wilkins ended up the one to get Buffy and Angel to seriously consider their relationship when he relates how painful it was to watch his mortal wife grow old and die while he stayed the same.
In the season 3 finale, Connor traps Angel in a box and drops the box in the ocean, theoretically for eternity.
In the episode "Hell Bound", there was a ghost who didn't want to got to hell, so he sent other spirits in his place. In the end, he was made corporeal and trapped in (another) box, destined to spend eternity not going to hell, but staring at a brick out the small window.
An immortal Nazi got chained up and dumped in a river for 60-odd years, coming to life and drowning every few minutes. When he finally gets out, he's a bit peeved.
Another adversary was left on a deserted island. After eating everything on it, he starved to death. Then came back. And starved to death again...
There was also an immortal who was one of Cleopatra's attendants, and ended up entombed for 2000 years. The likelihood that she repeatedly revived and then died again of asphyxiation in the sealed tomb isn't brought up in the episode, but it would explain her insanity when she got out.
Killian, after committing war crimes during WWI, is locked away, and after a few years, completely forgotten. The tribunal who sentenced him were initially going to execute him, but Duncan, the only witness, wanting to keep him from wandering off after his execution, argued he was insane, and thus deserved 'mercy' and life imprisonment instead. (Screw the Masquerade, apparently.) 80 years later, when he eventually gets out, he decides to return the favour.
Another immortal blames Duncan for leaving him to be burned at the stake. He then proceeds to graphically describe the feeling of his skin and organs burning and regrowing.
Arvin Sloan of Alias is currently trapped under large rocks in a tomb, several hundred feet underground and alone but he is alive and seemingly immortal. It is implied that his fate is to spend eternity trapped in this place.
Henry from Forever dies and comes back quite a bit, and comments that dying still hurts regardless. He can often be rather blase about a painful death (killing himself with poison to get a test result without the three week wait for example), but when he's faced with the possibility of having to go through being dissected again, he starts panicking and packing his bags immediately.
In "Xanadu" by Rush, the narrator clearly regrets having become immortal, since now he is trapped in the Pleasure Dome forever, the stars do not change, and he has clearly gone insane.
Type O Negative's "Suspended in Dusk" is about a vampire who has been dealing with being unable to be out in daylight or feel "the comfort of a grave" as well as seeing his "loves grow old and wither" over the past 400 years.
Mythology And Religion
In Greek Mythology, the gods are immortal to the extent that nothing can kill them. But they lack full regenerative powers, resulting in lasting injuries.
Uranus got castrated by Kronos.
Hephaestus was left with a permanent limp after getting in the way of his father's Masochism Tango.
Prometheus can regenerate, which isn't fun when his liver is torn out of his body every day by a hungry eagle. Also, according to the ancient Greek drama, the chains that hold him to the rock include a metal spike going through his chest. Unusually for Greek myths, this has a happy ending; Heracles slew the eagle and broke the chains that held him.
Chiron the centaur was gifted with immortality, but was allowed to renounce it when accidentally shot by Hercules: the arrow, poisoned with the Hydra's bile, caused an unhealing, festering wound, unable to kill the centaur but causing him constant agony. In some version of the myth he was freed when he gave up his immortality in exchange for Prometheus's freedom and was placed in the heavens as the constellation Centaurus or Sagittarius. Other versions have him somehow give his immortality to Prometheus, who was already immortal. The copyists probably made a mistake somewhere.
Hell. Revelations refers to it as the Second Death, but that's because of its finality and totality, not because those cast into the Lake of Fire are annihilated. Far from it. The inhabitants are immortal and not consumed by the flames, but quite capable of being tortured by them.
Oh, and there's also that part where in order for Jesus to die and fulfill the prophecies throughout the rest of the Bible, he had to subject himself to the most painful death penalty the Roman state could muster. At the end of "Good Friday" he had the skin flayed from his back, nail-sized thorns driven into his head, nails driven through all four limbs, severe life-threatening sunburns... and he was awake for every second of it.
In Norse mythology, Loki at one point gets drunk, crashes a party, and starts listing all the other gods' faults. Whereupon the other gods kill one of his sons, tie him to a rock in a cave with said son's guts, and hang a snake above his face in such a way that the snake's venom drips into his eyes. Forever. And they wonder why he starts Ragnarok.
Captain Scarlet and the Mysterons: Captain Scarlett is a Mysteron body double who regained his identity after falling off a building. He is indestructible because his body will regenerate after being killed, but that apparently doesn't make death any less painful for him. Which may explain why he seems so grumpy all the time.
In the Touhou project, Fujiwara no Mokou and Kaguya-hime both have resurrective immortality and hate each other's guts, so they spend their time killing each other.
The boss fight against Mokou involves killing her over and over and over until she's in too much pain to move any more. The youkai member of each party then tries to convince the human member to rip out Mokou's guts and eat them to gain immortality (or in Yuyuko's case, contemplates doing it herself; how immortality would affect somebody who's already a ghost is unclear).
On the other hand, Mokou seems to have developed enough pain tolerance that she finds it preferable to continuously freeze or starve to death than to heat her house or gather food. Despite the fact that with her power of complete control over fire, it should be a trivial exercise to heat her house.
Darth Sion in Knights of the Old Republic II inverts cause and effect; he's immortal precisely because of his vast number of painful injuries, taking the regular Sith ability to draw power from their own pain and rage and using that power to keep going despite the fact he shouldn't even be able to move without falling apart. Attacking him with weapons accomplishes nothingnote It would make things worse, except he's already so battered any further damage is just a drop in the ocean, and he only goes down after the Exile points out he isn't getting anything worthwhile out of his undead existence.
In The Exiled Prince, from the Dark Parables saga, this is the curse upon The Frog Prince. He remains young and handsome while his princess grows old and dies. And then he turns back into a frog, and stays one until he meets his second wife. And then he goes through the same thing with her, and then his third wife, and then his fourth.
Part of the Neverwinter Nights mod Shadowlords 5 took place in a town where nobody died, ever. One of the sidequests involved a woman who was buried alive in a trunk by a guy with an "If I can't have you, nobody can" attitude, while a minor encounter involved killing a bear which had been attacking another woman over and over again. If questioned about it afterwards, she shared the story of how she was once pinned down by a pack of ravenous wolves and it took a week for them to eat enough of her legs to become full.
Clinkz, the Bone Fletcher, from Dota2. A demon was causing destruction around The Hoven, and a mage cast a spell that would grant eternal life as a reward to anyone who killed it. Clinkz went to fight the demon, not knowing that he would become immortal doing so, and was blasted with hellfire just as his final arrow killed the demon. The result is that he is immortal, but covered in eternal flames.
The Nameless One from Planescape: Torment. As seen in the title, "torment" is a recurring theme of the game and the immortal protagonist has suffered so much, both physically, emotionally and spiritually, from his immortality that he's essentially become a Doom Magnet through the power of belief. It's implied his presence represents a concentration of suffering so potent it's slowly killing the Multiverse.
In El Goonish Shive, Nanase can create a "fairy doll" proxy body. She doesn't die if the doll is destroyed and can instantly create a new one. She does, however, feel everything the doll feels. In Wrath of God, she must keep Abraham from killing Ellen, using only the fairy doll spell and the newly-acquired "fey punch" spell. Abraham destroys every doll, yet Nanase has no choice but to keep coming back.
In Homestuck, Her Imperious Condescension communing with Jadethreatens a painful death if Roxy doesn't cooperate with her plans. She then points out that, as the victim is a god tier and has conditional Resurrective Immortality, it probably won't stick, which means she'll be able to do it over and over again, "until you finally get tired of dying and follow your orders".
The Immortals of Sithrak in Oglaf aren't immune to injury at all, though they do at least seem to have a very high pain tolerance. At one point Morag is beheaded, and only able to describe how it happened when somebody blows air up through her severed windpipe. Word of God says she's still just a head.
Also of note is that he had just traded the Healing talisman to one of his teammates because he thought having Healing and Immortality was redundant— not realizing that the Immortality talisman doesn't include healing or prevent injury.
The Robot Chicken short "Jesus and the Argonauts" has Jesus leading half of the Argonauts on adventures and getting them killed while fighting monsters due to his pacifist ways. Whenever he gets killed, cue angelic choir and pillar of light, and he's back on his feet again. At the end, he gets clubbed into the ground by a cyclops, resurrects, and gets clubbed ad-infinitum.