This is going to be a long post:
Let’s see what I can remember:
Jon Snow and the Night’s Watch: The Watch has a force of 300 men in the Wilds, trying to break the back of a huge Wildling force marching on the Wall. After digging in, though, they’re attacked by the Others, who were thought to be only legend. Their weapons were useless against the assault, save for Sam’s obsidian(or dragonglass) dagger, which killed an Other. The survivors of the battle try to make their way back to Castle Black, but many of the men revolt and most of the survivors, including Lord Commander Mormont are killed. Sam manages to save a wildling woman and her baby from the men who revolted, and the three of them end up at Castle Black.
Jon, meanwhile, has been ordered by the Halfhand to join the Wildlings, discover their plan and then return to the Watch. He’s sent as part of a small party that scales the Wall and attempts to take Castle Black from the rear. Before the attack, Jon escapes to warn the Watch. The Wildling army then attacks the Wall from the front, and with most of the officers and rangers spread along the Wall, Jon ends up commanding the Watch in the battle and manages to stave off several attacks.
After King Stannis arrives to decimate the Wildling force, the Watch begins preparations for the expected attack by the Others. Jon Snow ends up being voted as Lord Commander of the Night’s Watch after a bit of trickery by Sam.
Stannis and Davos: After getting mauled when trying to attack King’s Landing by Tyrion, Lord Tywin and Mace Tyrell, he returns to Dragonstone to lick his wounds. After Davos appeals to Stannis’ sense of honour, Stannis goes in aid of the Night’s Watch.
Robb Stark, King in the North: Robb returns from his campaign in the East married to Jeyne Westerling, breaking his vow to marry a Frey. Walder Frey immediately recalls all of his forces to the Crossings. Rickard Karstark sends several men to murder several Lannisters who were held prisoner, after Catelyn freed Jaime Lannister in exchange for her daughters and Jaime’s pledge not to take arms against House Tully or House Stark. Robb executes Karstark, and all of the Karstarks desert him as well. Edmure Tully, now Lord of the Riverlands after the death of his father, agrees to marry a Frey in exchange for Walder Frey’s renewed loyalty. Frey’s forces were needed to take back the North from the Ironmen, who invaded after Robb’s campaigns in the Riverlands left the North mostly unguarded. Edmure’s marriage was a trap, however, and Walder Frey has Robb and Catelyn executed, takes Edmure prisoner, and his forces decimates Robbs’.
Jaime Lannister and Brienne Tarth: Catelyn frees Jaime and secures from him a promise to return her daughters. Brienne was charged by Catelyn to see Jaime safely to King’s Landing, and then see Arya and Sansa safely to Riverrun. Along the way, Jaime is captured by a company of sellswords of uncertain loyalty. Jaime manages to save Brienne from being raped by telling the sellswords that she is worth a large ransom if she’s unharmed, but unfortunately doesn’t think to do the same for himself, and the sellswords end up cutting his hand off before turning him over to Roose Bolton, ostensibly one of Robb’s bannermen. Bolton ends up sending Jaime and Brienne along on their way to King’s Landing. After they arrive, they discover that Arya disappeared back when Eddard Stark was captured and is presumed dead(ha!), and that Sansa disappeared after Joffrey’s wedding. With Catelyn dead, Jaime charges Brienne to find Sansa and protect her, trying to begin to atone for his sins by keeping to his bargain with Catelyn.
King’s Landing(Lord Tywin, Tyrion, Sansa, Joffrey, etc): After the battle for King’s Landing, Lord Tywin takes up his position as the King’s Hand, relieving Tyrion. After Robb is killed, Sansa is thought to be the last living Stark, and thus the heir to Winterfell and the North. Sansa is married to Tyrion to give the Lannisters a claim. Tyrion takes pity on his 13-year-old bride and tells her that he won’t consummate the marriage until she’s ready.
As part of the deal that brought the Tyrells to the side of the Lannisters in the battle, Joffrey pledges to marry Margaery Tyrell. At the wedding, however, Joffrey is poisoned, and Cersei has Tyrion arrested for the murder. Sansa disappears from King’s Landing that night, and it’s presumed that she was a part of the murder as well. Tywin and Cersei essentially frame Tyrion, so he demands a trial by battle after Oberyn Martell agrees to fight for him. Martell poisons his opponent, Gregor Clegane, but is killed, so Tyrion is condemned to death. Before he is executed, though, Jaime frees him. Tyrion kills his father, Tywin, before escaping in a ship headed for the Free Cities.
Sansa and Littlefinger: After escaping King’s Landing, Sansa finds herself with Petyr Baelish(Littlefinger). Littlefinger marries Lysa Arryn and becomes Lord Protector of the Vale. He then kills Lysa and has a singer, Marillion, framed for the Murder.
Arya: Arya is captured by Lord Beric Dondarrion’s outlaws, who plan to ransom her back to her family. The outlaws also capture Sandor Clegane(The Hound), who fled King’s Landing during the battle. The outlaws try Clegane for murder, but he demands a trial by battle and wins, killing Lord Beric. Lord Beric is resurrected by Thoros of Myr, a priest of R’hllor. The Hound is freed, but the outlaws take his gold. In retribution, the Hound steals Arya away, as her ransom should be worth more than the gold he lost. Catelyn and Robb are killed at the Red Wedding, though, so the Hound heads to the Vale, hoping that Catelyn’s sister Lysa will ransom Arya. After a battle with several of his brother’s men, Clegane is injured and feverish. Arya escapes him and finds a ship bound for Braavos. She gives the captain the iron coin she recieved from Jaqen H’ghar, and is given passage.
That should be all the background you need to be able to read Feast, although I skipped Bran and Dany, who aren’t in the book.