They're united in their opinions that the EU's influence in national affairs should be significantly reduced, or that the EU should be abolished altogether. Even if they would be nationalist in the sense that you describe, this common cause would be a powerful uniting force.
More importantly however:
So, they promote their own country over others'.
[..]
Supposing that their respective countries would leave the EU, wouldn't they be on opposing sides?
"Nationalism" is a bit of a wrong term here, as most of these parties don't really believe that one specific nation is better than all other nations; certainly not like e.g. Nazis did, with whom the term "nationalism" is most often associated.
Instead, what most of them believe is that "Western culture" or "Judeo-Christian culture" is better than some other cultures, (usually Muslim/Arab, but sometimes also Eastern European), and they oppose the influence of those cultures in the native countries. I suppose we could call this "culturalism", and is in opposition to cultural relativism.
Another sort of "nationalism" that sparks opposition to the EU is also a bit different from what you describe, and can be summarized as "I'm proud of my country, and it's better off making its own decisions". It's better described as patriotism than nationalism.
Lastly, not all opposition against the EU is from nationalism. For example many consider it to be unnecessary bureaucratic, undemocratic, expensive, and unfair.
Many of these viewpoints are not exclusive to UKIP, AfD, FN, PVV, etc. by the way. There is a lot of Euroscepticism on the left too, although that usually focuses on some different issues than the right-wing parties do.