Можно ли написать Android Service, который нельзя стереть / отключить / удалить?
Service
Нет.Вы можете изменить прошивку, включив в нее свое приложение, и такие приложения могут быть удалены только путем замены всей прошивки.