Long John Silver in Treasure Island, to the point where its one of his defining characteristics:
Jim Hawkins (Narration): 'Then he [Silver] looked at me and nodded, as much as to say, "Here is a narrow corner," as, indeed, I thought it was. His looks were not quite friendly, and I was so revolted at these constant changes that I could not forbear whispering, "So you've changed sides again."
On the other hand, it's probably more appropriate to say Long John Silver's only on Long John Silver's side. He makes whatever alliance is most profitable or convenient for himself.
In the Hurog series, the nobleman Garranon. He's a good guy on his own, but whenever someone threatens his family, he is willing to do whatever it takes to protect them, resulting in many HeelFace Turn moments. More precisely, he's initially a nice guy whom Ward likes. He then makes it clear he's willing to support slavery to save his brother's life, and drugs Ward in order to carry him off to the king's asylum, when Ward gets in the way of re-enslaving a slave. Later, he helps Ward's cousin out with some money, and joins the heroes. Then, he drugs Ward again, after telling him that he has a son he has never even seen because the king keeps him at court all the time. Later, he's on the heroes' side again.
Lily in ''Soon I Will Be Invincible'. In that case it's less that the character is intentionally trying to play the sides, and more that the character has enough common sense to see that the "heroes" and "villains" aren't all that different.
Lord Gro from E.R. Eddison's pre-Tolkiensian fantasy The Worm Ouroboros. Not only is he an incredibly manipulative Magnificent Bastard, but he has a soft spot for the underdog. Thus every time he pulls off a successful plan (and this happens frequently), he immediately goes and switches sides to support the people he just screwed over. This makes him by far the most awesome character in the book. Unfortunately, the stress of being the only non-Blood Knight in his world eventually gets to him, and he goes berserk and starts randomly killing people from both sides in the middle of a battle, leading to his death.
Snape from Harry Potter quite often seems to be doing this. Numerous red herrings are thrown at the reader from all directions to make them think Snape is a bad guy one minute, and a good guy the next. Despite the reveal that he actually was on Harry's side all along, his actual integrity and preferred alignment is still up for interpretation.
In the Sword of Truth, the morally ambiguous Sister of the Dark Nicci gets the experience of serving just about every major faction. By the end of the series, she's gone from a totally innocent girl, to a supporter of the Fellowship of Order, to a respected Sister of the Light in service to the Creator, to a member of the secretive Sisters of the Dark who serve the Keeper of the Underworld, to The Dragon of the Imperial Order under Emperor Jagang, then known as Death's Mistress, to a True Neutral wanderer teetering between the sides as she fulfills her personal quest to discover the meaning of existence, to the hero's Black Magician Girl lieutenant. In the end, it turns out that she is ultimately on the good side, and she remains one of Richard's most trusted allies up to the end of the series and beyond.
Lampshaded in the Time of Troubles series by Harry Turtledove. A character is called a connoisseur of defection, changing sides five times. Both sides put up with him because he's such a damn good commander, and they feel that he can help them more while on their side than he can hurt them when he defects.
Jeb Batchelder. Went from Mad Scientist to helpful parental figure back to mad scientist, and he's been attempting to play the father figure again lately. Although another possibility is that he's been good the whole time and that his daughter Max refuses to let go of her hatred and accept that.
Sauron of The Lord of the Rings and The Silmarillion. In The Beginning, he was good, a servant of Aulë the Smith. Then Morgoth, Black Enemy of the World seduced him to the side of evil, and he left with Morgoth to rule in Middle-Earth. When Morgoth was defeated in an incredibly destructive war, Sauron had a true change of heart, and genuinely wanted to help with the reconstruction and make Middle-Earth beautiful again. He was too afraid to surrender himself to the Gods and potentially face retribution, however, so he took advantage of the reconstruction to set himself up as the next Dark Lord.
Computer Jack from Gone. He starts out the series as part of Caine's group, mostly out of fear. He seems to be considering a HeelFace Turn for a while, but Diana has to threaten him to get him to go tell Sam, the hero, how to survive his fifteenth birthday, saying that it's "time to do the right thing, even if it is for the wrong reason." He spends the first half of book 2 obviously on Sam's side, until Diana shows up and convinces him to pull a FaceHeel Turn and help Caine again. She does this by promising him "the ultimate technological challenge". He spends all of a few chapters on Caine's side, turns off the power permanently, and helps Caine remove uranium from the nuclear power plant. He's already wondering why he came back. He seems to disappear for a few scenes so that Sam and Caine can experience Enemy Mine and team up against Drake, and then he's back on Sam's side. He stays on Sam's side through the entirity of LIES, but he is also sick and not really in on the action at all. By PLAGUE however, he has finally accepted and grown into the hero mould permanently.
Diana describes herself as "Morally indifferent" and on her own side, meaning she basically sides with whatever team seems to offer her the most. Even her boyfriend Caine Soren has accepted this by HUNGER saying "Sure whatever. Be on your own side, I respect that." Diana is a strange case though, seeing as when Caine calls her out on being this (which she herself has openly admitted to being several times) she gets pretty pissed off about it, saying he's a ungratefulbastard and that she's actually "the only person who really cares about him", implying that perhaps her loyalty is finally settling down in the villain territory.
Except it isn't, Because she decides to go with Sam in PLAGUE breaking up with Caine whilst pregnant with his demon child. Damn. So now she's a hero right? Wrong, seeing as she goes back to team evil once her baby is born. But then seems to have a realisation that her daughters evil and seems to be trying to defy her. But oh, screw that, she's back on team evil by the end of the book.
Quinn is a interesting example. Starts off as thehero 's best friend, but then betrays him to join team evil, but then flips back again and decides to help Sam and essentially saves his life (he got him into the situation that nearly killed him, but anywhoo...), but by PLAGUE He's decided to stay with Caine in his kingdom of evil. Then in FEAR he's had enough of it, and rebels against it and is back to team good. But he might as well just sway with the wind.
In Revenge of the Sith's novelization, Anakin Skywalker veers between Palpatine and the Jedi in a way that's much less sudden than how it seems in the movie, even leaning several times back towards the Light Side. We all know where he ended up, obviously, but the pull of doing what Obi-Wan - who wants him to defend and protect people - and Padme - who wants to love and be loved - want are as strong as doing what Palpatine wants. It's just that Palpatine knew there was a contest going on and worked to throw it, though there were some tricky moments. Notably, after waking up on the slab and hearing that he's killed his wife, Anakin immediately tries to kill Palpatine with the Force - but he's so much weaker than he used to be that he can't, and then he doesn't want to anymore. Palpatine's the only thing remotely like an ally he has.
Simon Heap in the Septimus Heap series. He goes good guy-primary antagonist-Anti-Hero-good guy over the course of the series.
This applies to five out of six protagonists in Scorpion Shards, the exception being the Sacrificial Lion. All five go bad and good again at least once, and some do so twice.
Alex of the Alex Rider series starts off working for MI-6. During Eagle Strike, he leaves and becomes neutral, but then joins Scorpia after the events of that book. He then goes back to MI-6 after an attempt on Mrs. Jones's life goes wrong.
Lord Scourge in Star Wars: The Old Republic: Revan. At first, he is a loyal subject of the Sith Empire. Then, he is recruited by Darth Nyriss in the plot to overthrow The Emperor who plans to start another war with the Republic. Scourge, remembering the result of the Great Hyperspace War, in which the Sith were driven to near-extinction by the Jedi, realizes another war could well spell the end of the Empire. However, over the years, he realizes that Nyriss and her allies are too afraid to make a move and would rather play political games than do something to further their cause. Eventually, thanks in part to Revan's influence, Scourge allies with Revan and Meetra Surik (the Exile from Knights of the Old Republic II) in order to kill the Emperor. However, when they reach the throne room and are ready to strike, he has a vision of the Emperor's death and realizes it won't be then and there. Scourge betrays the Jedi, killing Surik, and gets Revan imprisoned for three centuries. The Emperor misinterprets this as proof of loyalty and makes Scourge his enforcer, who is also granted immortality.
In The Wonderful Wizard of Oz, the Winged Monkeys weren't bound specifically to the Wicked Witch, but rather to a Golden Cap. They're forced to follow the orders of whoever wears the cap to the best of their abilities. This includes the one who made the cap, the Wicked Witch of the West, and Dorothy.
The Bible gives us an Older Than Feudalism example in King Nebuchadnezzar, the best-known ruler of the Babylonian empire in the Old Testament. When first chronologically introduced, he was orchestrating the destruction of Jerusalem and taking many of the Jewish people captive. Later, through the efforts of the prophet Daniel in interpreting one of his dreams, Nebuchadnezzar turned to worshiping the true God and became a more noble ruler...only to later have Aesop Amnesia and attempt to burn Sadrach, Meshach and Abednego in his fiery furnace for not bowing to his statue of gold (they got better). Following that, he turned to worshiping the true God again...then sometime afterward allowed pride to get to his head and exalted himself, for which God punished him with seven years' madness. After THAT, Nebuchadnezzar had yet another HeelFace Turn, this time staying Face for the rest of his life.
The entire Israelite people, really, as portrayed in the Bible at least. They switch between following God with the utmost loyalty and ignoring His words completely near-constantly, typically depending on their leader at the time.
Ramsay Bolton in A Clash Of Kings starts out being a subject of the Starks. He then decides, in their absence, to kidnap Lady Hornwood, forcibly marry her, rape her, and then starve her. Ser Rodrik Cassel hunts him down and unwittingly captures him in disguise, and he is brought to Winterfell as a prisoner. Theon Greyjoy discovers him after usurping Winterfell, and he becomes his ally. He escapes Ser Rodrik's counter-siege on Winterfell, and raises an army of Dreadfort men. They arrive at the siege, ostensibly as Stark reinforcements, where Ramsay (disguised in red armor) betrays Rodrik, destroys the Stark army, and enters Winterfell, where he captures Theon and burns the castle to the ground. An interesting example because, while he's always an evil guy, the people who count him as an ally or an enemy changes with the wind.
Jaime Lannister could be considered one to some extent. His reputation as Kingslayer seems to have led to a case of "Then Let Me Be Evil" by the time the novels start. Following his gradual "HeelFace Turn" that begins in the third book, he still spends a portion of the fourth trying to subdue the "good guy" ally Tullys, although he is considerably more pragmatic about it than he would have been before losing his hand.
The mutineers who kill Lord Commander Mormont were criminals that were sent to the Wall. Many had committed heinous crimes, but some, such as Chett (who, granted, never got the chance to go through with the mutiny), while still being complete assholes had spent a fair amount of time in service to the Watch. "Averted" in the TV show
Sellswords in Westeros and Essos in general seem to have a habit of this, as they're loyal to whoever pays them and will usually abandon their employer if they get a better offer. Brown Ben Plumm is particularly fickle with his loyalties.
Jacin Clay from The Lunar Chronicles switches back and forth between being a hero and a villain throughout the series. He starts off as a background antagonist, a guard of Head Thaumaturge Sybil Mira. Later, he sides with the heroes and implies that he only works for the antagonists because he has to. Cue him betraying the protagonists to Sybil. Later, he makes another HeelFace Turn that actually sticks. This stems from his loyalties lying with whichever side is best for keeping Princess Winter, safe from harm.