The Alien Years, by Robert Silverberg, begins with an alien invasion from the perspective of a resourceful pilot. He's killed in the first chapter, and the rest of the novel focuses on his brother's family.
"Living Space": Clarence Rimbro, accountant and all-around nobody, is exactly the type of character Isaac Asimov likes to use as the protagonist in his stories, but once he's gotten the government to listen to his problem, agent Alec Mishnoff takes over as the person resolving the plot.
Battle Royale plays with this by trying to fool the readers in regards to Shinji Mimura. While the book starts off with Shuya as its POV character, Shinji Mimura gets made much of by several characters. Shinji does things early on that make it clear that he's cunning, and characters mention him to be the one that will think up a plan to have the class escape the game safe and sound. He even has quite a background to his character, especially with his uncle that taught him all sorts of things, and part of the book focusing on his plan to bomb the school. Shinji dies during the middle of the game, and while his death is made out to be one of the hardest hitting for most students, it becomes clear that the main protagonist was always Shuya.
Brave New World features perhaps one of the most iconic examples of this: we are initially led to believe the protagonist of the story is Bernard Marx, as the novel focuses on him being a misfit in the World State and his questioning of its ideals. Then, as soon as Bernard and Lenina arrive at the Savage reservation, we are introduced to John the Savage and the novel focuses more and more on John while Bernard fades into the background.
In Xenocide, Qing-jao is the focus of the storyline on Path. She doesn't die, (she does have her OCD/godspoken-ness taken away though) but she's very handily displaced by Wang-mu towards the end of the book, and though Wang-mu appears as a main character in Children of the Mind, Qing-jao does not.
In Empire, we meet Reuben Malich, who is basically the hero of the whole book except he gets unceremoniously shot in the face about two-thirds the way through, and Cole has to finish his work. Bonus points for the paperback version of Empire because it happens right before a page turn.
Card also uses it, by degrees, in Hart's Hope, which begins centuries before the protagonist is born, with the story of a baron who overthrows his king. Orem, the hero, isn't born until roughly one-third into the 300 page novel.
Cassie Dewell: The Highway starts like a direct sequel to Back of Beyond, with Cody Hoyt investigating the disappearance of his son Justin's girlfriend and her sister. However, about a third of the way through, Hoyt vanishes, and the plot switches to his partner Cassie trying to discover what happened to him, and uncovering an unholy conspiracy along the way.
The Cavaliers Series Oxford Blood opens with Stephanie French, social climber extraordinaire, attending the Cavaliers Summer Party and having Archie, the heir to a dukedom declare his love for her. And then Archie is turned into a vampire and kills her to complete his transformation. From then on, the action skips a year and focuses on Harriet, Stephanies cousin. Although Stephanie continues to have a major influence on the story, most notably by being the major motivation for Archies murder spree.
At first glace, Colin Lamb appears to be the protagonist of The Clocks. He's an "outsider" who gets mixed up in a peculiar murder case, and was let in the investigation thanks to his Friend on the Force, Inspector Hardcastle. However, Colin is actually a Hero of Another Story who is using the murder investigation to find new leads for his own Intelligence work, and Hardcastle serves as the primary sleuth working on the mystery.
Five chapters into The Cold Moons, the first protagonist Bamber dies. He is too exhausted from his journey and only survives long enough to warn the next protagonist, Buckwheat, about the humans.
Bamber's replacement Buckwheat is murdered twelve chapters in. His son Beaufort takes over as protagonist from then on.
Norman Partridge's Dark Harvest revolves around "The Run", an annual Halloween ritual in a Town with a Dark Secret, where the town's teenage boys are challenged to hunt down and kill a mysterious entity called "The October Boy" in exchange for getting permission to leave the town (which is otherwise forbidden). We're initially led to believe that the protagonist is Pete McCormick, a sixteen-year-old participant in the Run who enters for a chance to escape his hometown and start a new life. Then comes the Halfway Plot Switch, where it's revealed that the "winner" of the Run is actually murdered and resurrected as the following year's October Boy. It turns out that the real protagonist is the October Boy himself (real name Jim Shepard), who just wants to survive the night and put an end to the Run for good.
The Diamond Age by Neal Stephenson features a particularly spiteful example: as the book begins, we're introduced to a thuggish cyberpunk protagonist straight out of the low-rent sci-fi movies of the late Eighties, complete with spiffy black leather clothes, skull-mounted nanotech weapons, and life of petty crime. Within a hundred pages he's been gruesomely executed for armed robbery, and his neglected four-year-old daughter turns out to be the book's real heroine.
Bems And Bugs gives us Jacques, the Loveable Rogue who serves aboard the pirate ship christened as the Unexpected Charge. Eight chapters set up what promises to be a tale of high space adventure with a crew of loveable misfits. Then the story shifts to focus on the series' true protagonist, for whom pirates are simply prey to be hunted.
The first book has two Fafhrd and the Gray Mouser expies watching the city burn at the start. They have absolutely no impact on the plot and leave after doing some budget narration.
Though he doesn't die, in Guards! Guards! quite a few pages are spent making it look like Carrot is going to be the main character of the story, having all the traits of the classical hero, before Sam Vimes takes over as protagonist, not just of the book, but of the City Watch series. This was how it was intended to be, before Terry Pratchett realised Vimes had more character and switched protagonists.
In the second book, The Light Fantastic, the story's Deuteragonist and main protagonist of the Unseen University storyline is killed off a mere quarter of the way through the book, leaving Trymon, the Big Bad, unopposed at the university.
In Glen's Cook Dread Empire series this happens twice. First book looks like it will focus on The Storm Kings, a group of minor sorcerers trying to create an empire. But then they really screw things up and the narration switches to Mocker. And then, near the end of the first book, it is revealed that in fact Bragi Ragnarson is the protagonist of the saga. Although introduced almost in the beggining of the first book, at first he was portraited as a minor character. What's quite unusual, both the Storm Kings and Mocker remain as active, important characters throughout the series. That is, obviously, until they die.
Arthur Machen's short story, "The Dover Road". The first two thirds of the story stars Professor Warburton as he tries to come to grips with a bizarre phenomenon he and his colleagues have witnessed. Warburton eventually gathers up enough evidence to come up with a rational-enough solution that completely satisfies him. The focus then turns to one of the other witnesses, Ian Tallent, who had previously taken up all of 2-3 sentences in the story. Ian notices that Warburton's proposed solution fails to address certain aspects of the case and spends the remainder of the story doing some investigating of his own.
In Dragonvarld, it initially looks like Melisande might be the main character of the trilogy she's introduced first, she's tough enough to defy a dragon in Chapter 2, she's got a developed love interest, and she's in line to assume the position that the first book is named after (Mistress of Dragons). But then she spends the rest of the first book needing to be rescued and protected by other characters, being sexually violated (twice), and then dying while giving birth to characters who'll be important in the next books.
The Dynasty: In Jeff Benedict's account of the New England Patriots dynasty, the first hundred pages of the book focuses on Robert Kraft before drifting away from him and focusing more on Bill Belichick and Tom Brady, the relationship that occupies the bulk of the narrative. Drew Bledsoe is characterized as New Englands great hope for about seventy pages, but becomes a supporting character to the ascendant Tom Brady before being traded to the Buffalo Bills. Brady himself doesnt even appear until 153 pages in, at Chapter 16.
In the first Empire of the Ants book, the Ants part of the story starts from the perspective of a young male named 327, and follows him as he forms a team with female 56 and asexual warrior 103683... he is killed in the middle of the book, and his two partners take over as the main characters. And again later, 56 becomes queen and is reduced to secondary character then killed, while 103683 serves as the main character for the remaining of the trilogy.
In the description and beginning, the story seems to be a dungeon-diving adventure novel with a plucky young boy hero, until he is eaten by a dungeon mimic. Then you realize that the mimic is the real protagonist.
During the Ishgar Republic arc a Cat Girl named Keira Morgana is introduced. She is friendly (if a little scatterbrained), competent, in a lesbian relationship, and all around seems perfectly designed as a character for the readers to love. She also survives several chapters without Boxxy brutally murdering her, which is rare in this series. And then it turns out that she is merely Boxxy's facade to infiltrate elven society and learn a new Job. There was never a real Keira at all. There was even a Bait-and-Switch with a suspiciously strong student who seemed creepily interested in Keira, but he turned out to be just some random guy.
At the start of The Executioner and Her Way of Life, a boy is brought over from another world, and it seems like he will be the protagonist of the story as a boy Trapped in Another World, especially after he manifests a power. Instead, an executioner kills him, since otherworlders are a threat to the world, and the protagonist turns out to be another individual from another world.
Fade to Blue by Sean Beaudoin appears to have two protagonists, Kenny Fade and Sophie Blue. But later in the book, it's revealed that Kenny doesn't exist. He's a virtual life that Sophie has been living.
Humanx Commonwealth: In Quofum, Ersa Trellenberg is the initial viewpoint character, and seems to have all the elements unique appearance and backstory, adventurous but responsible, UST with the expedition's only female crew member expected in a heroic protagonist. Then he catches a lethal sonic blast to the forehead.
The third book in The Inheritance Trilogy, The Kingdom of Gods, plays with this; Shahar Arameri would appear to be the main character alongside the godling Sieh - she dominates the description on the jacket copy, at any rate but she actually gets shunted aside about 260 pages in to make way for her twin brother, Dekarta. (However, the author did state that she wanted to emphasize the plot, and thus the movers and shakers of the plot, rather than the romance angle...)
Jin Yong loves this trope. A majority of his wuxia novels start around an apparent protagonist, only to reveal (sometimes several chapters later) that it is not. The first comes to mind should be The Smiling, Proud Wanderer (笑傲江湖), where the audience is fooled into viewing Lin Pingzhi as the protagonist while it is actually Linghu Chong.
Joe Golem and the Drowning City has the opening chapter be from the perspective of Felix Orlov the magician and his experiences with dead spirits. He seems like the main character, but the second chapter shifts POV to his assistant Molly and she becomes the lead character throughout the rest of the book, while Felix is a Living Macguffin.
Highly pronounced in Susanna Clarke's Jonathan Strange & Mr. Norrell, where the titular Jonathan Strange is not introduced for 250 pages, before proceeding to gobble up most of the spotlight.
Cynthia Voigt's third Kingdom novel, The Wings of the Falcon, pulls this. Oriel is a dashing, brave, fantastically charismatic young man who is clearly the perfect candidate to win the heart of the princess and save the Kingdom. Until, of course, he dies in a duel about 3/4 of the way through the book. His always-in-the-background best friend, Griff, gets a rather abrupt promotion to Hero after that.
The Kingdoms of Evil: Pon, who appears to be a Farm Boy on his way to seek his fortune. You know, before he's slaughtered.
Jack Vance's Lyonesse trilogy begins with the birth and upbringing of the spirited Princess Suldrun. At about the halfway point of book one, however, she dies. The rest of the series divides its focus amongst a number of other characters, including her lover, son and father.
In the first Marcus Didius Falco novel, the spirited young noblewoman who encounters Falco, Sosia, seems to be the second protagonist, but then she's murdered. The actual second major character and Falco's love interest is her cousin, Helena.
The Course Of Honour appears to be Caenis' story, but in reality, it's the story of the rise of Vespasian, seen through Caenis' eyes.
Les Misérables opens with a book detailing Bishop Myriel's life and philosophy, firmly establishing his character. Then in the second book comes bursting through his door a certain parolee named Jean Valjean
Played straight in Ben Bova's Moonrise. The first half of the book has playboy astronaut Paul Stavenger as the main character, only to have him die about half way through. Following a Time Skip, Paul's less interesting son assumes the role of protagonist.
Mostly Harmless: A bizarre example crops up in a novel Arthur is reading while living with a race of human-like people who lack desires. Halfway through the story, the main character dies from dehydration, without any warning whatsoever. Arthur has to backtrack several chapters to find a line mentioning that the plumbing in his house was broken, meaning he couldn't drink any water and just didn't bother going anywhere else. He's not even replaced by another character; the story just meanders on about other stuff until it hits the standard page limit and stops.
In The Night of the Generals (later made into a film of the same name), during World War II, an officer of German military intelligence is investigating a series of murders of prostitutes, and comes to the conclusion that the killer is a German general. Two-thirds of the way through the book, he confronts the murderer, and is killed. Years later, a friend of his, who had a very small role in the story before this point, takes up the case and brings it to a successful conclusion.
Eponymous character of Narrative PoemPan Tadeusz by Adam Mickiewicz, Tadeusz Soplica is set up to make readers believe he is the main character, but as the story progress it becomes more and more apparent that the real protagonist is Father Robak, formerly known asthe infamous Jacek Soplica.
The first chapter of novel centers around a fairly Brainless Beauty named La Sorelli, who is given a disproportionate amount of detail describing her physical appearance, personality, and history for someone who turns out to be one of the most insignificant characters in the book. This is particularly Hilarious in Hindsight considering the losses the real heroine Christine endures to her personality in adaptations, reducing her to The Ingenue who vaguely resembles La Sorelli, personality-wise.
Played with, as while Christine is technically the heroine overall, the narrative actually follows the POV of her Love Interest Raoul and him uncovering truth behind Christines mysterious teacher/suitor for most of the novel. Towards the climax when Christine is captured, it switches perspective to the Persian who is more competent and knowledgeable about the Phantom. Its not until during the Scarpia Ultimatum and resolution, that it becomes clear that its been Christines story all along.
Most of Anthony Price's spy thrillers feature David Audley as the protagonist or a significant supporting character. The prequel The Hour of the Donkey introduces Nigel Audley, David's father, within the first few pages, demonstrating a family resemblance in attitude and intelligence. He is killed off before he gets a chance to learn about the main plot, and the usual Audley role is played by another character, who is identified as a previously-unnamed mentor David recalls in one of the novels it's a prequel to.
In The Rose Labyrinth by Titania Hardie, it initially appears that the two main characters are Lucy King, a young woman about to undergo a heart transplant, and Will Stafford, a young man travelling Europe in search of a family secret. However, several chapters in, Will is mysteriously killed in a motorcycle accident, and it's up to his brother Alex and Lucy to uncover the mysteries that await.
The Secret Garden: Mary is the protagonist of the beginning, and Colin, who's something of a Walking Spoiler, only meets her about a third of the way through the book. He slowly becomes more focal toward the end; Mary doesn't even have any lines in the last chapter.
The Septimus Heap series focuses more on Jenna Heap rather than the titular protagonist Septimus Heap; even the summary of the first book has an inclination to her story rather than his. He was the one most sought after by the antagonists for his Magical Seventh Son powers (though these powers never really manifested in the series), yet she had more of a narrative focus, and in the final battle she orders him not to help her fight the bad guys. She seals the evil away and is later crowned as queen, with everybody having absolute faith in her ability despite her age. He makes no protest about her telling him not to fight (despite his own desire to protect the family he was separated from since birth), doesn't comment on it later, does not fulfill a character arc and seems perfectly content with how things turned out.
The Silerian Trilogy: Josarian, the Firebringer, is prophesied to at last free Sileria. At first he leads the struggle and seems well on his way to doing this. Then he's betrayed and murdered as part of a deal to get the Valdani out, and revenge for killing Kiloran's son. Tanses takes up his role in the next books and serves as the main protagonist.
The Snuff Network starts off focusing on a former mobster named Russell Wheeler seeking revenge against the people who murdered his daughter. By the end of the first book, Russell fails to kill the man responsible and is shot to the death by the police. The remaining three books in the series hardly mention Russell at all, instead focusing on two new characters who turn out to be the real protagonists.
Each and every prologue is told from the point of view of a character who turns out to be a Sacrificial Lamb. The trope really only applies to the first book, because by the second book the reader will have figured out the pattern and not expect the character to survive.
The main act is Eddard Stark, the Lord of Winterfell and leader of the protagonist-heavy Stark family. While we see many points of view, the main action of the story centers around Lord Eddard; he gets loads of character development, hints at a fascinating past, the works. And then the Lannisters chop his head off before the first book even ends. In retrospect, considering the number of protagonists that are his children, his role can be reinterpreted as The Mentor.
Viserys Targaryen is a Decoy Antagonist. As the abusive and insane scion of a royal line deposed by our decoy protagonist, he looks like the main villain of the series, but he dies about halfway through the first book. After marrying his sister Daenerys to Dothraki horselord Khal Drogo in order to gain an army to invade Westeros, he quickly grows frustrated over how little regard Drogo and even Daenerys have for him, leading him to push his luck too far and die a gruesome death, which underscores how insignificant he really is in the grand scheme of things.
Inverted with the POV Stark children Bran and Sansa: while they have very little importance in the main plot in the first three books (especially Sansa, who until book 3 serves only as a secondary POV in King's Landing), at the end of the fifth book they grow more powerful and get reintroduced into the plot in a way or another.
In Strange Fruit, Tracy Deen is not even the first viewpoint character to be introduced, but still appears to be the protagonist for many chapters, being caught at the center of a Love Triangle and faced with a difficult decision about what to do about the pregnant girlfriend he regrets he wouldn't be allowed to marry. He makes his decision halfway through the story, and it gets him killed.
Machen did this again in his novella, The Terror where he makes himself the main character for the first few chapters before being demoted to mere Greek Chorus.
Margo Smith is the hero of the first Time Scout book. Skeeter Jackson steps in for the second and carries much of the rest of the series.
Tortall Universe: In the Trickster's Duet, Aly is the viewpoint character, but one of several chosen to create a rebellion that will put the prophesied queen on the throne; the beautiful, passionate and caring Sarai. At least, so it appears for the first 2/3rds of the story, until Sarai goes off and elopes to another country, leaving her little sister to become queen.
Andrew Phelan in The Trail of Cthulhu. It seems like he'll be something of a Supporting Protagonist or an Action Survivor, witnessing the bizarre goings on that may or may not be connected to his mysterious new employer, Professor Shrewsbury of Miskatonic University...but that's only for the first chapter. After this, he is no longer the POV character and eventually all-but-disappears entirely. He doesn't die, though, and considering this is a Cthulhu Mythos yarn, that's really saying something.
The original novel version of The Unholy Three has the titular, murderous three as the main characters until the fourth or fifth chapter; afterward, the focus switches to a young man named Hector who has the misfortune of crossing paths with the three. Averted in the movie adaptation (coincidentally Lon Chaney Sr's only sound picture), where the focus remains on the three even after Hector is introduced.
In The Walking Dead: Rise of the Governor, the two main characters are Philip and his ineffectual brother. Philip is the name of the Governor in the comics and it seems apparent that the novel is about him. Before it ends, however, Philip is killed and Brian takes on his name. Thus, the story was about him.
Sara Douglass's The Wayfarer Redemption series takes an interesting take on this. The main protagonist of the first three volumes is Axis. Initially, it seems that his love interest is Faraday. However, partway through the series, Axis falls in love with and marries Azhure, relegating Faraday to a supporting role. The first half ends on an apparently final note with Axis defeating Gorgrael, after Gorgrael kills Faraday and tears her body apart in a hopeless attempt to distract Axis. Then the second half begins with Axis retired and the kingdom in the hands of his eldest son Caelum. The first volume strongly pushes Caelum as the main protagonist, only for him to be rather unceremoniously cut down by Qeteb, turning over the reins of the series to his disgraced younger brother, DragonStar. Oh, and Faraday returns from the dead to become Drago's love-interest.
In the Doctor Who novel Prisoner of the Daleks, Stella seems like a perfect companion figure for the Doctor, but she gets killed off by Chapter Three. This sets the Darker and Edgier tone for the book.
This was also done in the Doctor Who Missing Adventures novel Time of Your Life, focusing on the Doctor's first adventure after "The Trial of a Time Lord". Angela is set up as the new companion, only to get killed pretty quickly. Instead it's Grant Markham who ends up as a companion by the novel's end.
The Zero Game: The apparent protagonist is murdered four chapters in, with the narration switching to his friend.
Nita is unquestionably the protagonist of Market of Monsters, but she gets a Decoy Deuteragonist in Fabricio. The plot kicks off when Nita's evil mother kidnaps Fabricio with the plan to sell his blood and body parts one by one until he dies and she sells the rest of the body (it's illegal but common in this world), and Nita finds the courage to defy her mother and set him free. When she takes him to the bus station, the reader fully expects her to run away with him to avoid whatever punishment her mother would have in store for her and the story to follow the two of them on the run together. Even Fabricio expects it. But she doesn't. Fabricio leaves alone, and Nita doesn't meet her future partner Kovit for several chapters.
The Worm Ouroboros opens with an Englishman named Lessingham being taken to the planet Mercury to witness the war going on there. Lessingham quickly becomes a Forgotten Framing Device as the story focuses on the major players of the war between the Demons and the Witches. Interestingly enough, Lessingham would return in a later trilogy author E.R. Eddison wrote as a proper protagonist, and would reference events in The Worm Ouroboros from time to time.