Except it is all in chroot, so uninstall aliendalvik and it will be gone, the described situation of reflashing/resetting device to be still malwared should not be possible (sure there might be other exploits, but then it will be using some generic linux bugs/0days on top of android exploits that have to work in the emulated form, there definitely are holes, but you have two layers to get through)