I thought I would share this deck with the forum to use/dissect as you wish. In our local meta (GTG Games-Midlands) there was a drought of Stark cards so I abused the lack of knowledge of what the Northerners can do.

Essentially its job is to maintain control of the field and beat the opponent to death with the Siege Of Winterfell Agenda. There is a heavy toolbox element in my variation of this deck but this incarnation is a little more straightforward and I'm too lazy to post both. However Grey Wolf x 3, Kennels and the Riders Of The Red Fork are the core (dropping Heralds to x 2)

Agenda

Siege Of Winterfell

Plots

Valor Morghulis

March To The Wall

Search & Detain

Building Season

Storm Of Swords

Respect The Old Gods

-I have recently being using Loyalty Money Can Buy in place of Respect the Old Gods -

Characters

Brienne Of Tarth PoTS

Deepwood Mercenary

Peasant Defenders x 3

Hungry Mob x 3

Hodor

Bolton Refugee x 3

Catelyn Stark LoW

House Umber Berserkers x 2

Robb Stark LoW

Host Of The Bear

Meera Reed

Wolf Herald x 2

Riders Of The Red Fork

Cat O' The Canals

Locations

Winterfell Castle (cos Starks live there)

Lord Eddards Chambers

Street Of Steel

Great Keep x 3

Frozen Outpost x 2

Narrow Sea x 3

Frozen moat

Bear Island

Xaro's Home (Be careful playing this if you need Bear Island to go off)

Northern Fiefdoms x 3

Attachments

Icy Catapult x 3 (I abuse this to hell)

Frozen Solid x 2

Ice

Grey Wind LoW

Northern Steel x 3

Needle

Events

Weasels Way x 3

Endless Endurance x 3

Winter Is Coming x 2

Nightmares x 2

Distraction

Lethal Counterattack

Getting a big drop on Turn One is important. If you cannot drop at least 3 cards and with confidence then its Mulligan time. I usually get a 4-5 card setup. The operation of killing characters is relentless and is basically what makes the whole deck tick. If your opponent tries to use anything that will prevent character death it needs to be dealt with immediately. There are plenty of ways to make this happen in the deck, choose your targets carefully and make sure that attacking you is costly to them.

An obvious tactic is killing and discarding my own guys. The combo's of Icy Catapult, Berserkers, Meera, Cat, Northern Steel, Ice etc come up frequently. Its biggest enemy is another Stark deck. Use Xaro's to gain card advantage. Bring Catelyn on to the table to strip their hand. Use the plots to keep the character count as low as possible. A swarm can be handled with catapults and berserkers but its costly, Valor might be a better option but try to use it only when you have a very good chance of earning power on the turn you play it.

Something about this post is screwy for me, might be one of those weird FFG Forum errors, but anyway, my initial thoughts...
You only listed 6 plots.
-I have recently being using Loyalty Money Can Buy in place of Respect the Old Gods- imho, that's a bad idea, RotOG is pretty much an auto-include in any Stark deck.
It's really really character-lite, I feel like any sort of control deck or targetted kill deck would handle it pretty easily; maybe thats why you said other Stark decks are a weakness, but I think Lanni kneel, Targ burn, Black Cells, etc would keep your characters in check pretty easily. I also think a decent GJ deck could save against your kill effects long enough to pull out the win.
Why no Lucas Blackwood? Seems like an auto-include when using the Beserkers, and fits your kill theme.
Street of Steel will also cancel Bear Island.
No Guard at Riverrun?

"Bring Catelyn on to the table to strip their hand" not sure what you mean by this...

The Plot count was an oversight. The missing plot is Snowed Under.

Respect the Old Gods is just not needed in this deck. You should always be able to play the characters that you want too with the locations available, The initiative is low and the claim isn't really needed. You have that much kill in the cards that the plot is better off as something else as far as it goes with me.

The deck is character light, you are right, and I deliberately trimmed it to the least possible count before it falls apart. I often test out additional Deepwoods but I usually end up back to one.

Lucas looks great on paper but I just can't rely on it happening. I can't waste a search on him and I suppose its luck of the draw but he just never appears when I need him too.

Regarding Bear Island and Street of Steel it is never a problem, you play what you need to play. This said I recently swapped SoS out for another Location, this time out of house. Again, you play what you need. SoS was not a 'must have' location and was dropped for that reason, not for its conflict with Bear Island. The new location gives a little more robustness to my hand and makes use of a few existing combo's and expands the value of some existing locations.

'Arrdets' Targ Burn is a nightmare to play against but its a fight. If a deck in his hands struggles then I know that lesser players/decks will really feel it. Getting Winterfell to the table ASAP is the first place to start.

I've destroyed every Lannister deck I have played against so I have no comparison there. Choke was tough at first but once I had my strategy sorted it became no problem. Don't know what Black Cells are so no comment I'm afraid.

I worded the Catelyn part badly. 'Stripping the hand' sounds a lot more impressive than, being 'used to hit a weakened hand.' Which is what she can do when you go totally on the offensive. Apologies.

Finally Guards At Riverrun. These are a TOUGH choice to drop but I rarely got to use the effect. I'm currently looking at a new way to incorporate a little more draw power (my new location is part of this) so these guys may return.