Das ist alles genau richtig. Gut, dass Du so formal vorgegangen bist - anders macht man nämlich leicht Fehler.
Dein Ergebnis: Es gibt ein Land, in dem jede Stadt nicht Hauptstadt ist, ist logisch vollkommen richtig. Es ist oft so, dass sich so ein Ergebnis komisch anhört. Man kann dann versuchen, es sprachlich besser zu formulieren, muss dabei aber aufpassen die Logik nicht zu ändern.
Hier könnte man sagen: Es gibt ein Land, in dem keine Stadt Hauptstadt ist. Oder noch kürzer: Es gibt ein Land, das keine Hauptstadt hat. Oder: Es gibt ein Land ohne Hauptstadt.
Und schon klingt es nicht mehr so komisch. Und klingt sogar (hoffe ich) ganz klar wie die Negation der ursprünglichen Aussage.
Aber wie gesagt: schön vorsichtig beim Umformulieren.