Para deixá-lo como nativo basta instalá-lo em /system/app. O problema é que, para fazer isso, o Android precisa estar rooteado, o que implica em ser possível desistalar o app.
Se o app tiver permissões de administrador também não poderá ser removido, mas é só retirar as permissões que a desinstalação pode ser feita. Em suma, repito o que disse acima: eu ficaria muito puto se instalasse um app que não permitisse a desinstalação.
Tem outro truque que pode ser feito: um intent filter pode capturar a desinstalação do app:
<intent-filter>
<action android:name="android.intent.action.MAIN" />
<category android:name="android.intent.category.LAUNCHER" />
</intent-filter>
<intent-filter>
<action android:name="android.intent.action.VIEW" />
<action android:name="android.intent.action.DELETE" />
<category android:name="android.intent.category.DEFAULT" />
<data android:scheme="package" android:pathPattern="seu.pacote.do.app" />
</intent-filter>
O problema é que mesmo assim é possível remover o app indo pelo terminal e removendo o apk manualmente (mesmo sem root, caso não seja um app de sistema).
Como você pode ver, a menos que você tenha o controle do dispositivo (algo como um smartphone corporativo ou sendo o próprio fabricante, por exemplo) não poderá impedir o dono de fazer o que quiser. E isso sem levar em conta que o aparelho pode ser rooteado.