Если местом вашего рождения является Украина - Вам можно получать гражданство Украины. Среди основных документов - свидетельство о рождении и листки убытия из России (выписка из ЖЕК).
Всю процедуру можно оформлять без Вашего присутствия. Вы можете оформлять все документы через посольство. Тогда выезд в Украину будет не обязателен.