The North:
House Stark: Brandon Stark, the Builder. His sons Benjen Stark and Bowen Stark. They would have the loyalty Cerwyn, Mollen, Cassel, Hornwood, and maybe a couple minor ones The Houses of Tallhart, and Karstark don't exist yet. They would have an alliance with Woodfoot, through Brandon Stark's marriage to Erena Woodfoot, William's sister.
House Bolton: Ralton Bolton, the Skinner. His children, Lyra Bolton, Jonnel Bolton, and Penna Bolton. They would have the loyalty of Lightfoot, Locke, Ashwood, Ironsmith, and Flint of Widow's Watch.
House Umber: Hoarfrost Umber, the Giantsbane. His children Harwood Umber, and Bethany Umber. They would have the loyalty of all the Clansmen.
House Woodfoot: William Woodfoot, the Half-Hand. His son Torrhen Woodfoot. They would have the loyalty of Glover, Forrester, and Bole
House Ryswell: Dorren Ryswell, the Steed. His daughters, Sybelle Ryswell, Barbrey Ryswell, and Alys Ryswell. Alys Ryswell became pregnant with the bastard of an unknown man, giving birth to a son, Helman Ryswell. They would command the loyalty of Dustin, Long, and Lake.
The Riverlands:
House Mudd: Jonothar Mudd, the Apostle. His children, Jyanna Mudd, and Garrett Mudd. They would have the loyalty of Teague, Mallister, and maybe a few minor houses, such as Erenford?
House Blackwood: Hoster Blackwood, the Wise. His children, Quentyn Blackwood, Danwell Blackwood, and Carellan Blackwood. They would have the loyalty of Tully, Keath, maybe some of the minor houses?
House Bracken: Manfryd Bracken, the Whimsical? His children, Joseth Bracken, Emphyria Bracken, and Marianne Bracken. They would have the loyalty of perhaps Deddings, and Justman, a couple of the minor houses?
House Fisher: Mallador Fisher, the Unlucky(or maybe the Gentle)? His children Theomar Fisher and Catelyn Fisher. They would have the loyalty of Mooton, Cox, Harroway, Towers, Darry, a couple of other minor houses?(Since, according to semi-canon sources, Fisher was wiped out by the Stormkings, I would think that they'd be situated near Harrenhal, except, it wouldn't be called Harrenhal...)
Maybe one other house could try to be kings, like Piper, or Vance, maybe even Vyper? Any ideas?
The Iron Islands:
House Greyjoy: Greydon Greyjoy, the Malevolent. His sons, Dykk Greyjoy, Norne Greyjoy, Harlon Greyjoy, and Aladale Greyjoy. Now, here is really where it is tricky; I imagined, that sitting in Nagga's Hall(off the coast of Great Wykk), that the Grey King rules from there. Greydon is the son of the Grey King, and so Greyjoy commands Goodbrother, all the houses there, Saltcliff, etc.
House Harlaw: Urrigon Harlaw, the Reaver. His son, Bennarion Harlaw. Naturally, they would command the houses such as Volmark, Stonetree, Myre, and Kenning.
House Greyiron: Quellon Greyiron, the Cruel. His children, Qhored Greyiron, and Gwynesse Greyiron. I guess they would rule over Blacktyde, Orkwood, and Hoare. If I remember correctly, they ruled from Orkmont, until they got destroyed by the Andals, right?
The Grey King, I imagined, could be like say... the Pope. He just sits in Nagga's Hall, and he issues orders from there. I don't know if it can be done, but I think that would be pretty epic. However, I don't know if youcan change it where he can live for say... a couple thousand in game years? Just a thought, not mandatory, but I thought it would be neat.
The Westerlands:
House Lannister: Lann Lannister, the Clever. His two sons, Garrison Lannister and Lyonel Lannister. Now, another complicated part. I imagined, that they only owned Faircastle, Kayce, Lannisport, and Casterly Rock. Let's just say, if it can be done, there are rebel settlements located where Crakehall is, or other places. When you conquer them, a script shows up that asks if you want to grant a heroic lord the regions settlement, after they swear fealty to you. You accept, and say, for example, Crakehall was taken, the script would say: Do you wish to grant the conquered settlement to the Heroic soldier who led the vanguard and took the settlement? You say yes, and then a general pops up in Crakehall, with a family tree. I don't know if this can be done, but I think that would also be epic!
House Reyne: Damion Reyne, the Bloody. His children, Leonella Reyne, Genna Reyne, and Gareth Reyne. They would have command of the Serretts, Marbrands, and Lefford, maybe a couple minor houses.
House Tarbeck: Lucion Tarbeck, the King-of-Cruelty. His sons, Geralt Tarbeck, and Horace Tarbeck. They would rule Westerling and Banefort.
The Reach:
House Gardener: Garth Gardener, the Greenhand. His children, Emmon Gardener, and Cynthia Gardener. I imagined them having command of Old Oak, Brightwater Keep, and Goldengrove.
House Redwyne: Forely Redwyne, the Drunkard. His sons, Gyles Redwyne and Willas Redwyne. I thought they could have the Hightowers, Maybe Sun House?
House Tarly: Harreld Tarly, the Merry. His children, Mathis Tarly, Horas Tarly, and Rylene Tarly. I figured the would have the whole, Longtable, Cider Hall, Ashford, Bitterbridge region? Is that reasonable?
The Vale:
House Redfort: Hosteen Redfort, the Bulwark. His sons, Robbett Redfort, and Harley Redfort. I figured they'd have the Redfort, maybe to the Eyrie, and possibly Heart's Home?
House Royce: Arcill Royce, the King-Who-Wears-Bronze(I ran out of creativity... yolo.... I am disgusted with myself). His children, Lyarna Royce, Rorarch Royce, and Atticus Royce(I just read HtKaMB again...). They'd rule Runestone and Gulltown, but would have strong spearmen.
And here, we would need to make up houses. Because, the only houses in the vale that have ancestry tracing back to the First Men, are the Redforts confirmed. So, I don't really know what to do here... Maybe make some houses that could be Quote-Unquote, related to the tribes of the Vale? I don't really know! Any ideas?
The Stormlands:
House Durrendon: Durran Durrendon, the Godsgrief. His son, Alesander Durrendon. They would rule over Tarth, Fell, and Buckler.
House Connington: Galladon Connington, the Quarreller. His children, Marya Connington, Barristan Connington, and Corenna Connington. They would rule over Swann, and Grandison.
House Wylde: Allard Wylde, the Poet. His children, Ravella Wylde, Arianne Wylde, Jeyne Wylde, and Maric Wylde. They would rule over Estermont, and Mertyns