I'm going to create a completely system-agnostic answer here, but it will probably apply to you, especially considering the example of A Song of Ice and Fire.
The reason that characters can drop like flies, even semi-randomly, in A Song of Ice and Fire without it detracting massively from the story, is because the story isn't about them. If someone whose tale you enjoyed dies, his story generally doesn't end there. What he did in life, how he died and what he was hoping to accomplish carries on into the future, influencing other events and the actions of other characters. The specific person may die, but the struggle over who gets to sit on the Iron Throne continues. Two houses might have some more enmity between them, but both Houses live on. (Even if you kill most of its members.)
So I think if you want to have a highly lethal game, you should try to emulate that. Don't tell the story of "Bob the Wizard and Jim the Fighter Find The Magic Gizmo And Save The Kingdom", instead tell the story of "The Magic Gizmo And The Twelve Groups Of People Who Want It".
I think that you'd need a change a few things to make it work, but it might turn into a very worthwhile and different kind of campaign. I would approach it something like this:
Scrap all preconceived ideas of where the story will go
Since this story will not be about any specific characters and there will be no good or bad side, it should not have a set direction. Instead, let it flow where it will. To some, this is normal, to others, it's a chance, but I think in a game like this it's a must. What makes A Song of Ice and Fire work is that for the most part, nobody has a clue who the good guys are and where the story will end. We want that feeling.
Present a situation/object worth fighting over, without assigning good/bad sides or fixed abilties
To keep the story going, there needs to be something that generates conflict, but it has to be something that isn't hamstringed into only doing a single thing. A Gizmo that can save the world from invasion by aliens isn't a good fit here, because it only does one thing and everyone will want it for the same reason. The One Ring is roughly in the same basket. But the Iron Throne on the other hand? You can do lots of things with it. The crown to a kingdom, an artefact that gives considerable (but not absolute) magical power to the wielder, a hoard of gold of incredible value, these are good things. You need something that will make people fight for all kinds of reasons, without an outside observer immediately being able to say "this guy good, this guy bad".
Do not assign player characters. Assign players Goals.
Characters are just going to die, probably a lot. That's good, and people should still get attached to them because it makes better drama and involvement, but we don't want the character's player to slam into a wall when the dice (or another player) finish off his character.
So instead we assign players a goal and then we attach characters to that goal. So instead of Tim playing "Jim the Wizard Who Wants the Magic Gizmo To Save Someville", Tim will be playing "The People Who Want The Magic Gizmo To Save Someville" and today he will be "Jim the Wizard". Now, when Tim gets his character killed, he doesn't have to stop. In fact, during play he probably revealed numerous characters who share his player-goal and he can just jump into any of those in an instant and continue playing his Goal. He can even switch from time to time when his other character(s) are temporarily out of the spotlight.
Give your players a reason to work with the goals of other players
The next step is to make sure that play won't devolve into each player running around on their own. You need to make sure they intertwine their goals, or at least make it so that their characters think their goals are intertwined, so they work together. (Until the inevitable backstab, of course.)
For example, the goals of "Use the Gizmo to control the people of Kingdom A" and "Use the Gizmo to prevent a war between Kingdom A and Kingdom B" are not exclusive to each other and people fighting for these goals could very well align (even if one is a little darker than the other).
Sometimes, even the simple threat of an outside Goal that interferes with both can be enough to get a group to work together for a while. (And it'll generate loads of conflict because both sides know it's temporary and they don't like each other). If the NPC party of "Use The Gizmo To Plunge The World Into Darkness" is clearly winning, maybe even "Use The Gizmo To Subjugate Kingdom A" and "Use The Gizmo To Bring Glory To Kingdom A" might work together for a few days.
And finally: Don't let characters hold back
Since the setting has to be lethal and we've set up the entire story to not be about specific characters but about a source of power and the struggle for it, characters can die freely without blocking anything. So make sure they do. While in most games, one player's character backstabbing another's would grind most of the story to a halt, this one is set up for it to not be a big deal, so make it not a big deal. (Give them a cookie every time they pull it off or something.)
Since the players are running a Goal, losing a person dedicated to it is probably not a very big deal. (For the progress of the story and the player's ability to play. It might be a very big deal for the goal and the other characters, but that's a good thing. Drama!)
The only thing that would truly disrupt a player's ability to play would be the complete and utter destruction of everyone who is trying to accomplish his goal... but that requires so much scheming, plotting and interesting storytelling that A) you'll see it coming from miles away and have plenty of time to flesh out a new goal and B) it would be awesome