Здравствуйте, Павел!
А пробовали обратиться в посольство или консульство Украины за этой справкой?
Если этот вариант не пройдет или по каким-либо причинам неприемлем, то попробуйте действительно обратиться к нотариусу.
На мой взгляд, исходя из смысла ч. 1 ст. 26 Федерального закона от 15.11.1997 г. №
147-ФЗ «Об актах гражданского состояния», Вы имеете право предоставить любой документ об отсутствии брака:
документ, подтверждающий
прекращение предыдущего брака, в случае, если лицо (лица) состояло в браке ранее. В случае, если государственная
регистрация расторжения предыдущего брака производилась органом записи актов гражданского
состояния, в который было подано заявление о заключении брака, предъявление документа,
подтверждающего прекращение предыдущего брака, не требуется и орган записи актов
гражданского состояния на основании сведений, изложенных заявителем в заявлении,
устанавливает факт прекращения предыдущего брака на основании имеющейся записи акта
о расторжении брака. В этом случае лицо (лица), вступающее в брак, вправе предъявить
документ, подтверждающий прекращение предыдущего брака, по собственной инициативе;
(в ред. Федерального закона от 28.07.2012 N 133-ФЗ)
Какой конкретно документ следует предоставить здесь не говорится.