Тогда Данелия продолжил этот разговор уже с Ревазом Габриадзе, вследствие чего изначальный замысел режиссера радикально преобразился. Как из «Острова сокровищ» выросла совершенно самостоятельная «Кин-дза-дза!», так и из «Нашего человека в Гаване» родился лишь очень отдаленно напоминающий об этом романе сценарий и фильм «Паспорт».
Сюжет у Данелии и Габриадзе получился такой. Тбилисский хормейстер детского хора Якоб Папашвили является грузином по отцу и евреем по матери. Его еврейская жена Инга уговаривает мужа эмигрировать в Израиль. В Москву провожать Якоба, Ингу и их дочь Нану отправляется таксист Мераб — единокровный, но не единоутробный брат Якоба, внешне очень на него похожий.
В аэропорту Мераб обнаруживает, что купить шампанское для достойных проводов брата можно только в зоне ожидания. С паспортом Якоба Мераб легко проходит соответствующий контроль и приобретает шампанское, однако назад его уже не пускают. В поисках начальника, могущего разобраться в его проблеме, Мераб заскакивает в самолет, который тут же взлетает.
Так Мераб в считаные часы оказывается в Вене — пункте промежуточной посадки между Москвой и Тель-Авивом. В столице Австрии Мераба пытается затянуть в свои дела летевший вместе с ним авантюрист Боря, но Мераб предпочитает отправиться в советское посольство и устроить там стычку с недружелюбным дипломатом. В результате герой оказывается в полиции — и, чтобы не попасть в тюрьму за пересечение границы с чужим паспортом, он выдает себя за Якоба и отправляется в Израиль. Вездесущий Боря снова летит с ним.
В Израиле злоключения Мераба только усугубляются: одни принимают его за агента КГБ, другие — за наймита еще какой-либо иностранной службы, а потому никто не желает его выручать. После долгих мытарств Мераб наконец выходит на человека, готового помочь ему нелегально вернуться на родину. Таковым оказывается бывший советский разведчик Семен Клайн, страшно соскучившийся по любимому делу. Тогда-то Мераб окончательно переходит на положение злостного нарушителя государственных границ…
Вскоре после того, как у Данелии сложился в голове первый вариант вышеописанного сюжета, Андрей Кончаловский познакомил его с приехавшим в Москву американским продюсером Менахемом Голаном. Тот выказал заинтересованность данелиевской задумкой и предложил прислать ему подробный синопсис.
Данелии удалось уговорить Габриадзе (в то время Реваз уже почти отошел от кино, отдавая все время собственному Театру марионеток в Тбилиси) на месяц съездить с ним в Израиль, где и написать синопсис «Паспорта».
Ознакомившись с синопсисом, Голан, не говоря ни да ни нет, выразил желание прочитать теперь уже полноценный сценарий. Габриадзе и слышать об этом не хотел, так что Данелии пришлось вновь обратиться к Горину. Тот нашел выход — и познакомил Георгия Николаевича с юмористом Аркадием Хайтом, одним из сценаристов мультсериала «Ну, погоди!». С Хайтом Данелия сработался — и через три месяца на суд Голана был представлен законченный киносценарий «Паспорта».
Продюсер, однако, не спешил с ответом, а вскоре выяснилось, что он обанкротился.
Разумеется, Данелия прощупывал возможность снять картину привычным способом — за счет государства. Но с приходом перестройки советские режиссеры уже успели почувствовать, как диктат цензуры сменяется диктатом денег. Выходило так, что Данелия просто не смог бы снять «Паспорт» без поддержки забугорных продюсеров. Государство все еще готово было выделять постановщикам данелиевского уровня небольшие бюджеты, но «небольших» денег в случае фильма, львиную часть которого требовалось снимать в Израиле и Австрии, было абсолютно недостаточно.
Помочь Данелии пристроить свой сценарий за границей вызвался председатель «Совинфильма» (внешнеторговое объединение в системе Госкино) Александр Суриков. Он организовал режиссеру поездку на Каннский фестиваль — и там Данелия действительно нашел себе продюсера, хотя и не без труда.
Сценарий вызывал интерес у многих кинодельцов, но переговоры все они начинали с выдвижения двух условий: во-первых, фильм должен быть англоязычным, во-вторых, главную роль должна сыграть американская звезда. Для Данелии оба этих требования были неприемлемы: в его видении «Паспорт» должен был быть многоязычным фильмом (причем основные задействованные по сценарию языки — это русский, грузинский и иврит). А на главную роль режиссер изначально наметил Бубу Кикабидзе.
В конце концов Данелия сговорился с французским продюсером Константином Александровым — эмигрантом из Ташкента. Александров не возражал против многоязычности фильма, но в главной роли и он непременно желал видеть международную звезду, а не Кикабидзе, знаменитого только в Союзе. Данелия скрепя сердце согласился на это условие.
Вскоре фирма Александрова подписала с «Совинфильмом» договор, согласно которому съемки «Паспорта» в СССР оплачивает советская сторона, а в Австрии и Израиле — французская.