В апреле 1988 года Данелия отправился в США на переговоры с тремя американскими актерами, выбранными им из перечня, предложенного Александровым. Это были Гриффин Данн, Питер Рихард и Николас Кейдж.
В итоге Данн отпал сразу. Рихард подходил Данелии больше, хотя и показался ему староватым для роли Мераба. Агент Кейджа же, узнав о том, что в портфолио ни у Данелии, ни у Александрова нет международных хитов, сразу дал отказ во встрече с актером.
Данелия позвонил своему бывшему ученику Якову Бронштейну, давно живущему в Штатах, и тот просветил учителя, что Кейдж является племянником хорошего данелиевского знакомого Копполы (с последним Данелия подружился в 1979 году, когда Фрэнсис Форд представлял свой фильм «Апокалипсис сегодня» на Московском кинофестивале). В результате Николас Кейдж в тот же день прочел сценарий «Паспорта» и дал свое согласие на участие в этом проекте.
С легким сердцем Данелия отправился в Москву, где немедленно запустил картину в подготовительный период. Георгию Николаевичу удалось настоять на том, чтобы основной костяк съемочной группы состоял из его соотечественников. Оператором стал Вадим Юсов, художником — Дмитрий Такайшвили, композитором — Гия Канчели.
Во время выбора натуры в Израиле у Данелии произошел легкий конфликт с Александровым. Продюсер крепко обиделся на режиссера — и отправил директору «Мосфильма» Владимиру Досталю письмо о том, что отказывается сотрудничать с Данелией.
Взбешенный Георгий Николаевич вернулся в Москву и сразу стал подыскивать себе другой проект. Редактор объединения «Ритм» Роза Буданцева предложила Данелии прочесть сценарий Георгия Николаева «Звездный час по местному времени», который очень понравился режиссеру (в итоге отличный фильм «Облако-рай» по этому сценарию поставит Николай Досталь).
Через месяц Александров прилетел в Москву с извинениями, но Данелия не спешил идти на мировую. Режиссер выдвинул два условия. Во-первых, Александров не должен никак вмешиваться в съемочный процесс. Во-вторых, гонорар за сценарий Данелия потребовал увеличить с десяти тысяч долларов до ста.
После непростых переговоров Георгий Николаевич все же вернулся в проект. Однако теперь в нем не было Кейджа, который, как поведал Александров, передумал сниматься в «Паспорте» (только много позже Данелия узнает истинную причину неучастия Кейджа: сыграв в успешном фильме, Николас внезапно стал большой звездой, и фирме Александрова он уже был не по карману).
Решили было снимать Рихарда, но тот действительно отказался, сославшись на повышенную занятость. В конце концов Константинов предложил кандидатуру французского актера — и прислал Данелии фильм на кассете с его участием (ни актера, ни названия фильма Георгий Николаевич в мемуарах не обозначил). Француз Данелию устроил — но и на этом артисте пришлось поставить крест: он попал в серьезную автокатастрофу.
Следующего актера (и на этот раз уже последнего: если бы Данелии он не понравился, проект пришлось бы заморозить) Александров отправил на самолете из Парижа в Москву уже живьем. Это был Жерар Дармон — малоизвестный французский артист, происходивший из алжирских евреев. В 1988 году ему было 40 лет.
Завидев Дармона издали, ожидающий его в ресторане Дома кино Данелия почувствовал было укол разочарования: не то. Но когда Дармон подошел, поздоровался и они вместе сели за столик, Данелия неожиданно сказал:
— Поздравляю, Жерар, вы утверждены на роль Мераба.
На следующий день Данелия и Дармон уже летели в Тбилиси — изучать грузинский характер.
Вот так одним из самых удачных в истории кино воплощений грузинского характера стал франкоязычный еврей Жерар Дармон.
Конечно, «Паспорту» было далеко до популярности «Мимино», но нельзя не признать, что сценарии к обоим этим фильмам написаны на одинаково отменном уровне. Уже сцена перед начальными титрами «Паспорта» ничуть не менее живописна и остроумна, чем пролог «Мимино»:
«Поезд останавливается.
Из вагона выпрыгивает Мераб и начинает быстро собирать в карманы кусочки земли.
В дверях вагона появляется проводница. Кричит:
— Ты что вытворяешь? В тюрьму захотел?
— Извини, дорогая, брат навсегда в Израиль уезжает. Родную землю забыли взять!
За спиной проводницы показывается начальник поезда. Тоже кричит:
— Ты что делаешь?! У тебя, что, сын осла, совсем мозгов нету?
— Понимаешь, землю… — пытается объяснить Мераб.
— Разве это грузинская земля? Это щебень из Астрахани. Вон грузинская земля — три шага сделать лень».
Мераб — единственный главный герой фильма, остальные персонажи проносятся мимо него, как в хороводе; некоторые появляются снова, но ненадолго. Самый яркий из второстепенных героев — темпераментный мошенник Борис Чиж, явный наследник Остапа Бендера. Любопытно, что согласно начальному варианту сценария в финале выяснялось, что этот Борис — агент КГБ, причем настоящий, а не мифический, как Мераб.