Si se puede soñar, se puede lograr ;) De momento no conozco ningún método PÚBLICO para hacerlo, pero te aseguro que es posible.
Comienzan las ediciones
Por ejemplo, el robot de StackExchange me pidió que actualizara esta respuesta con más información, así que aquí hay un malware llamado "xHelper" y también matryoshka. https://securelist.com/unkillable-xhelper-and-a-trojan-matryoshka/96487/
Verás que en este ejemplo en particular, el kit abusa del privilegio Root para instalar xHelper de forma silenciosa copiando directamente los archivos del paquete malicioso a la partición del sistema (carpeta /system/bin) después de volver a montarla en el modo de escritura.
También tiene un kit hermano llamado Triada. Estos kits toman los pasos adicionales de hacer sus archivos de núcleo inmutables, y sobrescriben a la biblioteca del sistema /system/lib/libc.so.
Esto significa que tendrías que entrar en modo Recovery, chattr el libc.so a mutable, borrarlo y reemplazarlo por una versión buena, y luego reimaginar. ¿He mencionado que esta familia de malware elimina tu acceso Root? ;) Puedes ser muy malvado con Android o con cualquier sistema operativo si quieres.
Fin de las ediciones
En cuanto a tu segunda pregunta, los reinicios de fábrica suelen ser suficientes para sacudir las infecciones de malware, pero si tienes un adversario avanzado, puede entrar en partes del proceso de arranque que serían extremadamente difíciles de detectar y eliminar. Dicho esto, estamos hablando de atacantes de nivel gubernamental.
La mayoría de los programas maliciosos para teléfonos pueden ser eliminados desinstalando la aplicación ofensiva y/o incluso reiniciando el sistema. Si te fijas en los 'Exploit Brokers' que compran malware profesionalmente, una de las cosas más grandes y caras que pagan es la PERSISTENCIA. Eso es porque mantener el malware en el dispositivo es cada vez más difícil hoy en día.
Paz notdan