This is a spoiler-filled chunk of text about the upcoming fourth season of Game of Thrones. If you have not read up to A Dance with Dragons, then this post is dark and full of terrors.
The first three parts of this are heavily based on this article over at HBOWatch.com and this fan-made list over at IMDb. The next two parts are based on extrapolations, interpretations, and things I have seen in the flames of R'hllor.
Did you like Ed Skrein as Daario Naharis? Too bad, Daario is now played by Michiel Huisman. Did you like Ian Whyte as Gregor Clegane, the Mountain that Rides, last seen in Season 2? Too bad, Hafþór Júlíus Björnsson is now Gregor. Of course if you liked the Season 1 actor then you're still out of luck, Conan Stevens is still gone. Did you like Callum Wharry's portrayal of Joffrey's younger brother Tommen Baratheon in Seasons 1 and 2? Too bad, Dean Charles-Chapman is now Tommen, after portraying Martyn Lannister in two episodes of Season 3.
Prince Oberyn Nymeros Martell, the Red Viper of Dorne, as portrayed by Pedro Pascal. Tycho Nestoris, as portrayed by Mark Gatiss. Ellaria Sand, as portrayed by Indira Varma. Lord Mace Tyrell, as portrayed by Roger Ashton-Griffiths. Hizdahr zo Loraq, as portrayed by Joel Fry. Lord "Bronze" Yohn Royce, as portrayed by Rupert Vansittart. Lady Anya Waynwood, as portrayed by Paola Dionisotti. Styr, the Magnar of Thenn, as portrayed by Yuri Kolokolnikov. "Fat" Walda Frey, as portrayed by Elizabeth Webster. Ser Donnel Waynwood, as portrayed by Alisdair Simpson. The Three-Eyed Crow (!!!!!), Lord Brynden, as portrayed by Struan Rodger. Child of the Forest (!!!!!!!!), maybe Leaf, portrayed by Octavia Alexandru, who is featured in this fantastically creepy casting video:
As those last two additions to the cast tell you, anyone planning to read books 4 and 5 unspoiled before Season 5 of the show is apparently making a bad life choice, and should maybe be told so.
Sarine Sofair will be portraying Lhara. Deirdre Monaghan will be portraying Morag Craster. Saffie Jacobs will be playing a different 'wife' of Craster. Daniel Rabin will be portraying Lord Blackmont, a house aligned with the Martells. Lu Corfield. will be portraying Mole's Town Madame, who may be a stand-in for Zei. Jane McGrath will be portraying a wildling named Sissy. Sigur Rós will be featured, maybe as a band at the Purple Wedding? Joseph Gatt is potentially playing a wildling, maybe a Thenn. Hoji Fortuna will be playing an as-of-yet unidentified role which might be a very minor role. Gabrielle Dempsey will be portraying an innkeeper's daughter. Stuart Martin will be portraying "Savage". Robert Goodman will be portraying a Valyrian slave, presumably on the way to, or at, Meereen.
Following what is listed in IMDb's Season 4 episode cast listings, these are who, of the new cast, we should expect to see in which episodes. Sadly, this is not very informative.
S4E1: Child of the Forest, Mace Tyrell, Lady Waynwood, Hoji Fortuna's character, Hizdahr zo Loraq, Tycho Nestoris, 'Craster's Wife' (Saffie Jacobs), Styr, "Savage", Morag Craster, Oberyn Martell, Lord Blackmont, Three-Eyed Crow, Donnel Waynwood, Lhara, Yohn Royce, Ellaria Sand, Walda Frey.
This list is not realistic, even for a show as expansive as Game of Thrones. So this is just a placeholder list until the season gets closer to airing.
S4E2+S4E3: Mace Tyrell, Oberyn Martell, Donnel Waynwood.
The inclusion of these characters suggests more insular episodes, with scenes at King's Landing and in the Vale. Maybe a wedding, and the subsequent flight of someone away from King's Landing, takes place: the presence of Ser Dontos Hollard suggests this heavily.
S4E4: Mace Tyrell, Valyrian slave, Morag Craster
Some things will happen in King's Landing (aftermath of a wedding?), some things will happen in or around Meereen, and ... once again, not too sure where Morag Craster would be met. ASOIAF never suggests that the men of the Night's Watch revisit Craster's Keep after the slaughter there, so my competing guesses are that some of Craster's wives/daughter-wives make it to the Wall to ally with the Night's Watch, or they join Mance Rayder's army.
S4E5: Oberyn Martell.
More King's Landing drama.
S4E6: Oberyn Martell, Lhara.
Even more King's Landing drama. Whoever and wherever Lhara is, she appears.
S4E7+S4E8: Oberyn Martell.
Yet more King's Landing drama. After episode 8, Oberyn Martell doesn't appear any more, so, draw your own conclusions there.
S4E9: no character mention at all.
Rumours from Winter-is-Coming.net are that this episode will be a big action piece similar to Season 2's "Blackwater"; this time around it will be the Attack on the Wall.
S4E10: Bronze Yohn Royce.
The last episode of the season occurring at least partially in the Vale insinuates that someone gets pushed out a moondoor.
With the appearances of The Three-Eyed Crow and a Child of the Forest, and appearances by Tycho Nestoris and Hizdahr zo Loraq, it's evident that Season 4 of GoT is pushing into Book 5 territory while also finishing telling the story of Book 3. Which makes sense; of the 82 chapters of A Storm of Swords, only 32 have not yet been filmed, and they're not evenly distributed. The things directly in A Storm of Swords that still could appear on screen take place in a few different locations, with some much heavier in plot than others.
`Plotting between Sansa and Dontos (Sansa II)
`Tyrion interacting with Symon Silvertongue, Tywin shows off newly forged swords for Jaime and Joffrey (Tyrion IV)
`The Dornish host getting to King's Landing, Tyrion and Oberyn interacting (Tyrion V)
`Tyrion and Shae share some time with the dragon skulls (Tyrion VII)
`Joffrey is presented with Tyrion's gift, he hacks it in half with the sword Tywin gave him (Sansa IV)
`The Purple Wedding (Tyrion VIII)
`Sansa escaping King's Landing (Sansa V)
`Jaime and Brienne arriving in King's Landing (Jaime VII) - except that they already did, so...
`Tyrion's trial (Tyrion IX)
`Jaime confronts the Kingsguard (Jaime VIII)
`Tyrion's trial, concluded, and trial by combat (Tyrion X)
`Jaime assigns Brienne to find Sansa and Arya, gives her Oathkeeper (Jaime IX)
`Tyrion escapes prison (Tyrion XI)
Analysis: This should be enough for ten episodes of court intrigue and trials, particularly with the show's inclusion of material for Joffrey, Margaery, Olenna Redwyne, Cersei, and Tywin.
North of the Wall
`Meera Reed telling Bran about the Knight of the Laughing Tree (Bran II)
Analysis: The one chapter of Bran that hasn't been covered in Season 3 is heavy in exposition about the past. Game of Thrones likes putting that kind of content into the DVD extras, not on the show itself. So Bran's plot will move into A Dance with Dragons territory. How far in is anyone's guess.
`The Wall is attacked by the Magnar (Jon VII)
`Attack on the Wall, Jon must now lead the fight (Jon VIII)
`Jon gets thrown into an ice cell (Jon IX)
`Jon meets with Mance, Stannis's army shows up (Jon X)
`Sam and Jon deal with aftermath of Attack on the Wall (Samwell IV)
`Jon is offered the position of Lord of Winterfell (Jon XI)
`Sam sets up an election (Samwell V)
`Jon is elected the 998th Lord Commander (Jon XII)
Analysis: If Episode 9 contains most of the Attack on the Wall (Jon VII-X), then what the heck happens at Castle Black in the eight episodes before that? Presumably the election of the next Lord Commander (Samwell IV and V, Jon XII) will occur before the Attack.
`Arya dreams of wolves, Sandor and she kill a survivor of Red Wedding (Arya XII) - except that this already partially happened
`Sandor and Arya hang out at the Inn at the Crossroads, Arya leaves Sandor (Arya XIII)
`A Frey meets a dead fish (Epilogue)
Analysis: Arya has a lot of content in A Feast for Crows and A Dance with Dragons, so the show will probably move her plot forward rather than just stop after a chapter and a half. Since the showrunners do not show any evidence of being dumb, the Epilogue chapter is more likely than not going to end up being the final scene of Season 4.
`Daenerys's group gets to Meereen, and Barristan tells her of Jorah's treachery (Daenerys V)
`Daenerys is Queen of Meereen, dismisses Jorah (Daenerys VI)
Analysis: Daenerys's content is extremely light for the rest of A Storm of Swords, and part of it has already happened: we already know who Barristan Selmy is. So her plot will probably advance into A Dance with Dragons.
`Petyr and Lysa marry (Sansa VI)
`Sansa's family life gets even more complicated (Sansa VII)
Analysis: This might be all that happens in the Vale in Season 4; Sansa VII is also all-but-guaranteed content for the season finale.
A Storm of Swords has no content from Asha Greyjoy, so some more invented plots will occur for her. I guess Asha had to leave Pyke at the end of Season 3 so that she can return in triumph in Season 5 for a kingsmoot.
The Dreadfort and The Twins
Theon/Reek seriously does not need to get tortured on screen anymore but who knows what the showrunners will decide to do with him. Since Roose Bolton's new wife is a member of the cast for Season 4, apparently she (and probably Roose) will make an appearance somewhere. I have no idea how the show plans on incorporating the Boltons and Freys into the show for Season 4.
As the opening sloth photograph insinuates, very very slowly.