A bad actor ("Trudy") can flash any custom Android ROM, including a ROM that removes package certificate validation during APK installation. Thus, any query that your app makes to its Android host OS is essentially a request to Trudy.
So, it might be possible to uncover the installation of a hacked APK with an unadulterated OS. But with an adulterated OS, all bets are off.
I think any solution for the client to self-validate would necessitate an authoritative validation of the host OS. Not easy.
Is it somehow possible to use package signature in certificate
generation process to prove that self signed certificate originated
form untampered package?
(1) Do you mean that each client generates a different self-signed certificate after installation and somehow cross-references this against the apk package signature in order to authenticate? Then no, this will not stop Trudy. (And it would not be useful in authentication, either.)
(2) Do you mean that the client has a universal private key embedded in the APK and that metadata on the package certificate can be used to verify against the private key? I do not know offhand if there are any available fields in the package certificate metadata in which to add this information. This is an interesting approach that you suggest. However, since Trudy might be the OS, theoretically Trudy could mock any result it wishes. I do not see this stopping Trudy.
This (SO) post by a developer for Proguard offers 5 options for handling secrets in your Android app. He notes:
Intrinsically, nothing on the client-side is unbreakable, but you can
certainly raise the bar.