Что можно сделать нам как родным, чтобы его не депортировали?

Правовой статус после освобождения
Ваш брат – гражданин Украины (есть только загранпаспорт).
Он отбывал наказание в РФ, после освобождения у него нет правовых оснований для законного пребывания (нет РВП, ВНЖ или гражданства).
В такой ситуации МВД почти всегда выносит решение об административном выдворении/депортации.
 
2. Возможность остаться в России
Есть несколько путей:

Ходатайство о предоставлении временного убежища (ст. 12 закона «О беженцах», ФЗ № 4528-1).

Принимается территориальными органами МВД по вопросам миграции.
Если есть риск опасности для жизни и здоровья в Украине (например, в связи с военными действиями), это основание для предоставления временного убежища.
Заявление на РВП (разрешение на временное проживание).

Обычно подаётся в общем порядке, но у вашего брата ситуация осложнена:

наличие судимости (в РФ + непогашенная в Украине) — серьёзный фактор риска, так как п. 9 ч. 1 ст. 7 ФЗ-115 («О правовом положении иностранных граждан в РФ») прямо запрещает выдачу РВП и ВНЖ лицам, имеющим непогашенную или неснятую судимость за тяжкое/особо тяжкое преступление.
Обжалование решения о выдворении.

Если вынесут решение о депортации, можно обратиться в суд в течение 10 дней.
Основания для отмены: наличие семьи в РФ, постоянного места жительства, гуманитарные причины.
В ряде случаев суды учитывают невозможность безопасного возвращения в Украину (особенно если у человека есть близкие родственники – граждане РФ).
 
3. Судимость на Украине
Да, повлияет.
Российские органы могут ссылаться на то, что есть непогашенная судимость, а значит, препятствия для легализации (РВП/ВНЖ/гражданство).
Это почти наверняка станет основанием для отказа в РВП и ВНЖ.
Но при этом не является автоматическим основанием для выдворения, если есть гуманитарные обстоятельства (например, война).
 
4. Что можно сделать родным
Сразу после освобождения (или заранее через адвоката) подать от его имени заявление о предоставлении временного убежища. Это автоматически приостанавливает процедуру выдворения до рассмотрения.
Подготовить доказательства связи с РФ:

семья (родственники – граждане РФ),
постоянное место проживания (регистрация, жильё),
намерение остаться и легализоваться.
Если вынесут постановление о выдворении – срочно обжаловать в суде в течение 10 дней.
Можно ходатайствовать через адвоката о замене депортации на временное пребывание по гуманитарным основаниям (ст. 12 ФЗ-115).
 
Итог:

Без документов (РВП/ВНЖ/гражданство) вашего брата автоматически попытаются выдворить.
Судимость в Украине осложнит получение РВП/ВНЖ, но не лишает права просить временное убежище.
Самый реальный вариант – сразу подать на временное убежище и обжаловать депортацию в суде, ссылаясь на гуманитарные причины (опасность возвращения в Украину, наличие семьи в РФ).
 
 

Здравствуйте, Марина! 

1. В соответствии с Федеральным законом от 25 июля 2002 г. N 115-ФЗ «О правовом положении иностранных граждан в Российской Федерации»

1. Разрешение на временное проживание иностранному гражданину не выдается, а ранее выданное разрешение аннулируется в случае, если данный иностранный гражданин:

6) имеет непогашенную или неснятую судимость за совершение тяжкого или особо тяжкого преступления на территории Российской Федерации либо за ее пределами, признаваемого таковым в соответствии с федеральным законом;

Т.е. об РВП/ВНЖ здесь речи не идет. Ему откажут. 

2. Действительно, единственным вариантом здесь является подача заявления о представлении временного убежища в РФ.   

Порядок предоставления временного убежища регулирует Постановление Правительства РФ от 9 апреля 2001 г. N 274 «О предоставлении временного убежища на территории Российской Федерации». 

Как только он подаст заявление, ему выдадут справку о рассмотрении заявления о предоставлении временного убежища. Эта справка подтвердит законность его пребывания на территории РФ  на время рассмотрения заявления. После того. как он подаст заявление ему обязательно надо встать на учет по месту пребывания.

п. 5

Лицо, подавшее заявление и получившее справку или имеющее свидетельство о рассмотрении ходатайства о признании беженцем на территории Российской Федерации по существу с отметкой о продлении срока его действия, обязано встать на учет по месту пребывания в порядке и на условиях, которые установлены Федеральным законом «О миграционном учете иностранных граждан и лиц без гражданства в Российской Федерации».

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