This is why I think some kind of Clan/Family setup would help. I don't care about individual Hx, per se. I think you do need divisions between people, though. It should be factional rather than individual like Hx.
I think a lot of individualism would make it too modern. Rugged individualism might work for a modern apocalypse, but clan/family dynamics are more important in this period. That's why I think a straight Hx wouldn't work. You'd not capture the dynamic of blood ties and blood oaths.
As for group setup...
Asking leading questions solves many questions about the PC relationships, I think.
...
To illustrate, I use my theoretical setup... Vikings in Ireland. A bay by the sea with an Irish village and a Viking longphort. The Vikings have taken over the area.
(Except it's the Ireland that never was, of course. It's not actually Celtic Ireland, and it's not actually Vikings.)
The big, blonde, pagan raiders have conquered the village. Let's say it's been 5-10 years since the raiders took over. The people of the village are slighter, dark-haired people (who are all converts of the Roman religion through the work of missionaries)... they mostly hate their overlords, but they're mostly powerless to stop them at this time.
Players can be part of either the blonde pagan people, or the slighter dark-haired people who all worship the son-god of the Empire of Eagles... but being one race or the other doesn't necessarily imply something about the drama, even if it could. (Racism & religious intolerance being meaty reasons to do bad things.)
Furthermore... let's say the self-made Jarl of the pagan raiders has just died prior to the start of the game.
Who will take over? (Is the new Jarl one of the players? How did he gain the right to rule?) What if the old Jarl only had a daughter, and she did not have the right to inherit? What does that mean about the new Jarl? Who might challenge the new Jarl, and why? What happens to the daughter, and what happens if someone marries her?
(And do we assume the Jarl died of natural causes? Perhaps yes, perhaps no. And if the Jarl didn't die of natural causes, who murdered the Jarl and why?)
What happens in the village? Who might rise up, now that the Jarl is dead? Who amongst the blonde pagan raiders might ally themselves with the village in order to overthrow the new Jarl?
And what about the 50 men who serve the Jarl? 50 men, supported by a village of 300 people... the logistics do not add up. What did the old Jarl do to keep his men fed and happy? Raiding? Trading? Killing people in the village & stealing their things? What will the new Jarl do?
What would the neighbors think about the close proximity of a band of pagan raiders? What local lords might want to attack the new Jarl and expel the pagans from the land?
...
So, binding the PCs together shouldn't be difficult if you're asking the right questions, even if I think the game needs some faction/clan-based approach to allegiances (and not a Hx).
I think Apocalypse World doesn't make binding-together a requirement, though. It works well as disorder and chaos within a faithful reading of the drama of the world.