Rurouni Kenshin: Kenshin's quest to protect people and fight for justice without killing is his redemption for all the lives he previously took as an assassin. Both in the anime and manga, (but particularly in the anime, especially filler episodes or arcs whose stories were changed) he encourages other warriors to try to make amends and work towards making a better world rather than commit Seppuku when they fall into similar situations.
Blue Devil in Shadowpact is assigned a Redemption Quest by the Catholic Church, to make up for selling his soul for fame in Underworld Unleashed - which led to the death of his friend Marla - and also to try and counter the Family Unfriendly Aesop of a guy who sold his soul and subsequently gained demonic power being a high-profile superhero.
It later turned out the Church couldn't do anything to help him... after he completed all the quests.
Incorruptible, the companion story of Irredeemable has former supervillain Max Damage trying to be a superhero after The Plutonium, the Superman analogue becomes a Fallen Hero.
Film
A frequent theme in the Rocky movies. Apollo pursues a rematch with Rocky in the second movie so he can regain any respect he's lost from nearly losing to a bum, Rocky goes for a rematch with Clubber in Rocky 3 to erase the self doubts caused by the dramatic beating he got in their first fight, etc.
The Replacements a Keanu Reeves comedy football movie, has this happening to Reeves' character Shane Falco. Falco had notoriously choked in the final game of his college career, and performed miserably in his little time as a pro, so this last chance at the game represents a chance for him to erase that image.
At the same time, the film makes it clear that none of the replacement players, including Falco, became permanent professional players and went back to their original jobs (in one case, back to prison). This is despite the fact that they've accomplished what the original highly-paid "superstars" couldn't.
Played with but Deconstructed in the end in The Wrestler, where what would normally be the subject of Randy "The Ram" Robinson's Redemption Quest in most other sports movies (namely, his big reunion bout with his old sparring nemesis "The Ayatollah") in fact isn't; his real Quest is to redeem himself in the eyes of his estranged daughter and to make a connection with the stripper with whom he has fallen in love. He ultimately fails at both, and his decision to go ahead with the bout even if his heart problems mean it'll kill him is ultimately a symbol of his failure in this; he wins the bout, but it's heavily implied that he dies in the process.
The film The Fisher King has shock jock Jack Lucas (Jeff Bridges) helping the deranged Henry/Parry Sagan (Robin Williams) in getting a love interest and finding the Holy Grail, as a redemption for having inadvertently caused the death of Sagan's wife.
The film The Verdict starring Paul Newman as a middle aged, alcoholic lawyer taking a big malpractice case against a rich hospital.
The eponymous Mystery Team is out to regain the respect of their community.
In By The Sword, Suba is trying to make right what he did wrong at the fencing school he used to go to, what with him killing his maestro in a duel to the death.
Zee: L.T., those Africans are my people too. For all the years that we were told to stand down and to stand by, you're doing the right thing.
L.T.: For our sins.
Both: Hooyah.
Literature
In his Back Story, Dragonlance character Lord Soth was given a chance to redeem his soul after becoming a Fallen Hero. At first he leaps at the chance, but turns his back on preventing The End of the World as We Know It to confront his wife about accusations of infidelity.
In The Kite Runner, Amir seeks to redeem his past actions towards Hassan by rescuing his friend's son.
The Scarlet Pimpernel is Marguerite's quest to atone for unintentionally causing the execution of the Marquis de St. Cyr, one of the French aristocratic fugitives her husband Sir Percy has devoted his life to protecting.
The Silver Chair: Aslan assigns Jill the task of finding the lost prince Rilian as her Redemption Quest for causing Eustace to fall off a cliff.
Severus Snape spends most of the Harry Potter series atoning for causing Lily's death by protecting Harry from harm and working as a double agent for both the Death Eaters and the Order.
Brimstone: This is the entire premise of the show, where Fallen Hero Ezekiel Stone gets a second shot at life and a way out of Hell if he returns 113 souls that managed to escape.
LOST's Michael has a redemption arc in season 4 after killing Ana and Libby in season 2. He manages to save Desmond, Aaron, Sun, and maybe Jin before dying in the season finale.
Arguably, Caroline's idea to save $250,000 to launch the cupcake business, the driving arc of 2 Broke Girls.
Sam Winchester from Supernatural. After breaking the final seal which unleashed the apocalypse on Earth, Sam spends all of Season 5 by trying to fix the mess he created. Season 5 is often viewed as Sam's redemption by many viewers.
Stefan Salvatore from The Vampire Diaries. After becoming a blood-addicted Ripper who was controlled by Klaus for the first half of the third season, Stefan spends the other half of the third season trying to gain his free will back and turn on his humanity again. He tries to redeem himself for all of the immoral acts he committed during his Ripper phase by joining the fight in destroying Klaus.
Mythology
Heracles had to do twelve of them after killing his family in a fit of madness.
Susanowo must make amends after throwing a dead horse (amongst other squicktastic things) at his big sister's court. He brought back the legendary Kusanagi to her. It's not known how much of it was kicking arses and taking names, and how much of it was genuine remorse.
Tabletop RPG
Dungeons & Dragons Plothook #309: "The cleric tells you that before he will cast atonement on you, he wants you to do this for him, to prove your remorse is genuine..."
This was a suggested method of restoring a character of an alignment-restricted class who broke his code, in earlier editions; the Player's Handbook specifically refers to fallen Rangers having to seek atonement through deeds.
Paladins both play it straight and avert it: if one commits a Chaotic act, she loses her powers and must go on a Redemption Quest, but if she commits an Evil act, she loses her powers and no amount of redemption questing will ever bring them back.
Before Third Edition. Third Edition made it possible to Atone (via Atonement, as noted above) for committing an Evil act, and toned down the restriction on Chaotic acts so that it only applies for severe breaches of the Paladin's Code or being enough to shift the Paladin away from Lawful Good (both also solvable via Atonement).
This is a suggested plot thread for renegade Abyssal Exalts in Exalted. Redeeming the Abyssal Exaltation back into its original Solar form is explicitly possible- just very, very difficult. So difficult, in fact, that any PC who manages it will be, in the canonical setting, the first ever redeemed Abyssal.
Vampire The Masquerade had Golconda, a state where the vampire no longer has the impulse to kill people and only needs minimal blood to live eternally. The exact ways of achieving it have always been left up to the individual Game Master but the general recommendation was to make it an epic quest, throughout which the vampire in question has to feel remorse for her past sins and make amends as best as she can.
Video Games
It initially appeared that this sort of redemption was what Athena and the other gods had in mind for Kratos from God Of War, but it turns out that wasn't quite the case. They do forgive him. However, it was not forgiveness Kratos wanted, but to forget all the terrible things he had done. Gods do not grant him that. And that is why there are no more Greek myths.
The Light Side path of the entirety of the sequel.
In Prince Of Persia The Sands Of Time, the Prince strives to redeem himself by undoing the damage he inflicted upon the time-space continuum by releasing the Sands in the beginning of the game.
Thane Krios has spent the last few years killed despicable, evil people in penance for the years he spent as an assassin for first the hanar and then private individuals and organisations. He is also dying of an incurable disease. When he learns of Shepard's mission to take down the Collectors, he signs up immediately, seeing as the best thing to do with what's left of his life.
Subverted in Tali's loyalty mission. The Admiralty Board gives her (and Shepard, naturally) the task of reclaiming a quarian ship that has been overrun by geth. If she is killed, the Board promises to drop the charges against her. If she survives and succeeds, she still has to deal with the charges but the act will lend credence to her side. The subversion comes in where the admirals prematurely pronounce her as KIA and one of them suggests exiling her posthumously, anyway. This being a Role-Playing Game, the final decision is left up to Shepard's diplomatic skills.
This is effectively Cecil's story arc for the first half of Final Fantasy IV.
Red DeadRedemption. John Marston, former outlaw, is sent by Federal agents to hunt down and kill members of his former gang. It seems like a subversion at first because the Federal agents are actually forcing Martson to leave his peaceful retirement on a small farm by kidnapping his wife and son and threatening to jail or kill Marston for his life of crime, but through the game Martson talks about his desire to atone for all the violence he's committed and how much he hates having to keep killing people.
Tarnum from the Heroes of Might and Magic series spends his entire story arc trying to atone for the terrible deeds in his first life that barred him from entering the Barbarian afterlife. He was cursed with immortality and spent a thousand years fighting evil. Tarnum finally achieves redemption in Heroes of Might and Magic IV by guiding the young Waerjak as he unites the remaining barbarian tribes without repeating Tarnum's mistakes. However, when he is offered admittance into the afterlife he desired, Tarnum chooses to stay with his people, having found a new reason to live.
The first of the redemption tasks involves helping the soul of the man who killed him, the first Gryphonheart king. While Tarnum has reservations about this, he proceeds with the task, especially when he learns that the man's daughter, the current queen of Erathia, is Tarnum's own niece (yes, the entire Gryphonheart line is descended from Barbarians).
Umineko No Naku Koro Ni This is pretty much what Kinzo's life turned into after him raping his daughter, her giving birth to Yasu and Yasu being thrown of the cliff by Natsuhi. He desperately wants to be able say he's sorry and give Yasu his/her grandmother's gold. In an example of Redemption Equals Death, the moment Yasu manages to solve the riddle and Kinzo can say he's sorry, he dies.
Genji: "...After some sad incidents, Master's life... was completely reduced to atonement."
Web Comics
Villainous example: the driving force behind all Dimension of Pain stories in Sluggy Freelance is Lord Horribus seeking redemption for letting Torg escape, by hauling Torg's soul back to the demons' dimension for eternal torment.
Similar to the Avatar example, in TwoKinds, Keith is sent into exile for killing his father (though this was more to keep the father's good name intact by avoiding a trial) and the only way he could return was to bring back the human Grand Templar with him. He succeeds, though mostly by accident (he'd long since befriended Trace when the group discovered he was the missing Grand Templar)
Western Animation
Initially inverted on Avatar The Last Airbender, where Prince Zuko's Evil Overlordfather banished him for not being evil enough, with a hopeless Redemption Quest being Zuko's only means of ending that banishment. Zuko's true redemption quest then comes when he realizes how worthless the redemption his father offered is and instead pulls a Heel Face Turn in season 3.
An important aspect of restorative justice is about an offender making restitution to his victims. Unlike 'ordinary punishment', restorative justice is about making redemption voluntary and (hopefully!) genuine.
Michael Vick is a real life example of someone had one.
