Свой же ответ и публикую. К сожалению без картинок, сначала все сделал.
Стандартный способ:
1. Сделать полный сброс/восстановление телефона (это не наше, нам так не интересно)

Наш способ:
1. Делаем жесткую перезагрузку телефона (красная кнопка под нижней левой заглушкой).
2. Включаем телефон стандартной кнопкой включения.
3. Ждем включения телефона (экран снимать с блокировки не нужно). Опускаем "шторку" (Свайп сверху экрана вниз) и на вкладке "Быстрые параметры" заходим в "Параметры".
4. В меню "Безопасность" выбираем "Администраторы устройства" и снимаем галочку с вредоносной программы. При запросе выбираем пункт "Отключить". Запоминаем название зловредного приложения.
5. Возвращаемся в "Настройки", заходим в меню "Приложения", ищем наше Зловредное приложение и удаляем его.
6. Все - вирус удален.

P.S. данная инструкция верна для телефонов Sony Xperia серии Z и выше. Мне достался телефон с приложением с иконкой в виде Клубнички.