Гражданин Украины стал жертвой запрета на выезд из РФ из-за алиментных требований - как действовать в такой ситуации?

Алена, такое действительно возможно, пусть договорится с первой женой об оплате частичной алиментов и снятии запрета, это можно оформить как мировое соглашение на стадии исполнения.

Федеральный закон от 02.10.2007 N 229-ФЗ (ред. от 06.03.2019) "Об исполнительном производстве" (с изм. и доп., вступ. В силу с 17.03.2019)

Статья 50. Права и обязанности сторон исполнительного производства

1. Стороны исполнительного производства вправе знакомиться с материалами исполнительного производства, делать из них выписки, снимать с них копии, представлять дополнительные материалы, заявлять ходатайства, участвовать в совершении исполнительных действий, давать устные и письменные объяснения в процессе совершения исполнительных действий, приводить свои доводы по всем вопросам, возникающим в ходе исполнительного производства, возражать против ходатайств и доводов других лиц, участвующих в исполнительном производстве, заявлять отводы, обжаловать постановления судебного пристава-исполнителя, его действия (бездействие), а также имеют иные права, предусмотренные законодательством Российской Федерации об исполнительном производстве. До окончания исполнительного производства стороны исполнительного производства вправе заключить мировое соглашение, соглашение о примирении, утверждаемые в судебном порядке.

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