Prevent feudalisation and keep tribal affiliation of peasants and warriors and nationalisms could evolve from that.
That, in fact, is key, IMO. National identities (or call them tribal identities if you like, but its the exact same) have always existed, however always in varying strengths and forms. The Germanic tribes of the migration era and beyond that certainly had an identity. The early centuries of the East Frankish (i.e. German) Realm were marked by conflicts between Franks and Saxons, and that very much on a level of identity, as another example.
What changed all that was the rise of the nobility as an own class. Class consciouesness, over the generations, became much more important than national identity, and nobles had much more in common with each other than with their lower class compatriotes. Additionally, the rise of monarchs and nobles meant that states were now ruled according to dynastic principles, even if that means collecting far apart or ethncially very different territories (see the rise of the Habsburg Empire as example).
Hence when Enlightment and Revolution came, and monarchs and nobles were taken down some pegs, it was inevitable that national identity would be strengthened again, and hence that nationalism would come.
What is needed is to weaken monarchy, nobility and most of all the dynastic principle coming with it.