В досоветские времена выражение было таким: "Курица — не птица, баба — не человек", - это в словаре Даля.
А фраза "Курица — не птица, прапорщик — не офицер" приписывалась Петру Первому.
То есть каждый вариант с отрицанием строился по двучленной модели, а страны подставлялись.. .по ситуации. :)
Какая страна была первой «незаграницей» , сказать трудно. В мемуарном очерке востоковеда Виктора Робсмана, бежавшего в Персию в 1930-е годы:
...Белые стены, исписанные в разных местах короткими надписями, именами, фамилиями побывавших здесь до нас людей, бежавших из России. Некоторые надписи смешили, вроде: "Курица не птица, а Персия не заграница! " (Виктор Робсман. Царство Тьмы: рассказы и очерки бывшего корреспондента «Известий» . — 1956, с. 119.)
Подробнее об этом - на форуме
http://forum.lingvo.ru/actualthread.aspx?tid=115878 и в
http://otvet.mail.ru/question/46065294/ Из эссе Ирэны Грудзинской-Гросс "И. Бродский и Польша"
...Бродский (родившийся в 1940 г. ) и его сверстники вступили во взрослую жизнь в пору невидимого, медленного ослабления коммунистической идеологии. Ему не исполнилось и тринадцати, когда умер Сталин, в шестнадцать он застал «оттепель» , события польского «Октября» , революцию в Венгрии, потрясшие «социалистический блок» . Польша в те годы являлась незыблемой частью империи Советов, в полном соответствии с присловицей «курица не птица, Польша не заграница» . Однако в культурном, художественном и интеллектуальном плане эта страна была — относительно — открыта Западу. Использовать все связанные с этим преимущества — к такой цели стремились тогда интеллигенты из СССР и их польские друзья.
Литовец Томас Венцлова, друг Бродского зрелых лет, вспоминал, что, как и большинство его знакомых, прочитал «почти всю западную литературу по-польски: Пруста, Кафку, Музиля и даже Томаса Манна, потому что в Литве эти книги ни на каком другом языке было не достать. Покупали книги частью на черном рынке, частью в магазинах; из-под полы можно было разжиться даже Гомбровичем или Милошем.. .Мои приятели, начинающие писатели или просто образованные люди, выучивали польский очень рано, чтобы быть в курсе происходящего в мире. Конечно, это странно звучит, но даже от «Trybuna Ludu» [печатный орган польской компартии] был толк: из нее о мире узнавали больше, чем из «Правды».. .