Back to the question. A society with strong focus on the family might be a solution.
Can you say family feuds? In the old south, such things would go on for generations, as each family remembered the smallest slight and vowed to avenge it, creating an endless circle of violence.
And I wouldn't say nationalism has caused more deaths than any other idea. Wars and fighting have been going on as long as we could pick up rocks and talk to eachother. How do you think they justified such large scale actions against eachother then? Religion comes to mind. And religion has been a justification for the greatest atrocities since its conception and has a much longer head start than nationalism.
Nationalism (often supported by religion) can, with more advanced technology and more targets, do more than primitive religion and tribalism ever could have immagined. But do you really think that old Tribal Tom, or Religious Roger, or any Primitive Paul, had they been able to get their hands on advanced weapons, wouldn't have used them to slaughter their enemies by the tens of millions?
Nationalism can get a larger number of people behind a single idea, but that just makes it's potential larger in scale, not of type, than smaller tribalism or ethnicism.
Heck, religion can dwarf nationalism in that regard, because religion isn't easily stopped at borders.