Для получения визы требуется нотариально заверенное разрешение отца ребенка.

В разных государствах, разные требования . Во многих ( даже в большинстве ) требуется согласие одного родителя ( если например ребенок выезжает с бабушкой-дедушкой) . Но если ребенок едет с одним из родителей ( даже в разводе) - согласие второго не требуется ( собственный опыт пересечения границы с ребёнком с Литвой, Латвией а оттуда в Европу) Если визу на ребенка выдали в грамотной фирме ( а не тут, у тополя ) , то это уже определяет возможность пересечения границы.
P.S - лишение родительских прав отца займет у вас "вечность" ( собственный опыт, уже 2 года "ни коня ни воза").

Такую справку в полиции вам не дадут, вы сможете доказать что он пропал, думаю нет, а соответственно можете забыть о европе.

Не все так просто, как вам показалось. Полиция не сможет вам выдать справку о признании гражданина пропавшим без вести.
Ст. 42 ГК РФ. Признание гражданина безвестно отсутствующим
Гражданин может быть по заявлению заинтересованных лиц признан судом безвестно отсутствующим, если в течение года в месте его жительства нет сведений о месте его пребывания.

Вы должны подать заявление о розыске, полиция - провести определенные процессуальные действия, потом вы подаете в суд и получаете искомый документ.
Тот факт, что вы не общаетесь совершенно не говорит о том, что человек пропал и его невозможно найти.
В вашем случае-найдут. Вы попросите оформить согласие, он-денег за него. В конце концов вы подадите в суд, чтобы он разрешил данную ситуацию.. .

Св-во о рождении не просто аккаунт в одноклассниках... Запись в св-ве о рождении - это закрепление юридического факта и для ее и "исправления" надо тоже топать в суд.

Два месяца-улыбнули:)))

Без вести пропавшим считается через пять лет с момента подачи заявления, если хмырь не нашёлся.

только через суд!