Sartre wrote that the fundamental human relation was one of conflict. "Conflict" can mean a variety of things, but I think the most fundamental is the tendency of any subject to objectify every other subject. Our relation with the Other is to turn it into an object, and into a means. The outcome of this, for Sarte, was war betweem all people (although not necessarily a literal war). Constant escalation was the result as I try to assert myself as a subject by objectifying you, and you do the same.
There are interesting parallels between Sartre's almost pychogical anylsis and the political relationships in your paradox. One nation asserts its right to exist by threatening theother nation, and the other does he same. There are problems of immorality here just as there were problems of immorality for Sartre. In Sartre's philosphy, one has a responsibility to one's self to be a subject, otherwise one was in bad faith, was immoral. However, it seems to me that those who fulfilled to their utmost the imperative to be a subject would be the Napoleon Bonaparte's of the world. Therefore, what was moral in preserving one's own subjectivity was immoral as far as the other was concerned with its own freedom and subjectivity, just as in your paradox what was moral in preserving one nation's existence was immoral as far as the other nation's existence was concerned.
Levinas had a different answer to this conondrum. He purposed that "I" surrender to the Other. The expectation was that this would eventually work when the Other would behave in the same manner and mutually submit to me. (I do not think Levnas ever said or wrote that last part, in fact he said one never could expect such a thing, but I'm reading it into him anyway.) The question is can a policy of mutual surrender rather than mutual escalation work in the political world? What would have happened if, in 1980, we had suddenly told the SU, "that's it. we're not only not building any more nuclear weapons, we're destroying what we have."? Of course, ideally, mutual surrender would be great; the SU would reciprocate be destroying their weapons, and then the SU and USA would hold hands, and prance about together...
But, as silly as it may seem, mutual surrender seems to have a strong argument working for it. Or rather a group of similar arguments, everything from "treat others as you would be treated," to the cliche warning, "don't become your enemy, or you're no better." And of course there's Kant, too.
In sum, in tryng to find a way out of the paradox, there seem to be two roads. The first says to achieve an ideal end, one must take whatever means are necessary. This isn't really a way out of the paradox, but accepting it, and declare it as moral because of a privledgin of the "I" or "We" over the Other. The second path demands that to achieve an ideal, the first step must be in the direction of that ideal, not away from it, no matter the consequences. To achieve peace, practice pacifism. The Other comes before the subject. In this light, the paradox is how to balance the needs of the Other with the needs of the subject. Two of the most famous answer, we can't and we have to dominate (sartre), or we can't and we have to submit,(levinas), aren't very satisfying.
