Update in response to your edits in the question
You are correct that validating a cert up to the trusted root is not 100% foolproof. What it guarantees that a trusted CA issued this cert to the domain that you are communicating with (because you can check that the URL in the cert matches the URL that you are establishing the SSL connection with). This was how SSL was designed to work. If that's not good enough and you don't fully trust the CAs in the Android trust store, then there are still things you can do.
It sounds like what you are describing is Certificate Pinning. Here is a guide to certificate pinning by OWASP, which even has a section about Android. The idea is that you include either the public key or a hash of the full certificate of the root CA, intermediate CA, or server cert in the source code of your app. Since all Android apps get code-signed at build-time, you can be confident that the "pinned" public key will arrive at the device un-tampered. Unless the device is rooted (more on that below), you should be confident that it will remain un-tampered.
It's good that you're thinking about this very carefully. That's good. But, as @Limit said,
I think you are overthinking your problem :)
You are not the first person to think about this problem, and there are standard ways to solve it. You are making things much more complicated by trying to invent your own solution. A chain of signatures leading back to a cert in the OS trust store (or a pinned key if you want to go the extra mile) really is enough to guarantee that the certificate is real.
About rooted devices, you said:
nova days [now a days] even EPROMS are writable ???? if you can write into memory there is no such thing like immutability :)
besides rooted device is vulnerable for fs files altering
If your app is running on a rooted device (either rooted intentionally by the user, or by malware) then all guarantees and security proofs are off. There are some tricks you can do, but they are security theater at best. As far as real security goes, it's game over. I'm sorry but you're just going to have to accept that, unless you want to enter into an arms race with rootkit authors - which is well outside the scope of this site.
I also want to point out that while possible, the attack you're alluding to is very advanced. You can add code to your app to check the integrity of the binary against the code-signing signature, and refuse to run if the check fails. Here are some links from a quick google search:
With root access to the device, it is possible for a hacker to remove this check from your binary, but this will not happen from casual drive-by malware. It requires expert hackers to spend weeks reverse engineering your app. The kind of experts that you only find in government spy agencies and organized crime. It's time to define your threat model: are you worried that your app will be attacked by nation-states or organized crime? Yes / No?
No: then don't worry about it, doing certificate pinning and a runtime self-test of the code-signing will protect you even on rooted devices.
Yes: then stop getting advice from random people on the internet and go hire a real security consultant!
Your use-case seems a little strange. It sounds like you are trying to re-invent SSL, rather than using SSL the way it was designed.
In SSL, the server always presents a certificate to prove that it is the right server. The point of mutually-authenticated SSL (where both the server and the client have certificates) is for the device to prove to the server that it is the right device. Having the server send the client a key to decrypt the client cert is a bit like having the server prove to itself that it is the right server. ??
How does the client trust the server's certificate?
The client should trust the server's certificate only if it chains back to a root CA cert that is in the Java Keystore. If your server's certificate was issued by a public CA (ie you bought it from Digicert, or Verisign, etc) then the root should already be in the Android keystore. If it was issued by a private CA, then the right thing to do is to include the root CA's certificate in the app resources and add it to the Java Keystore on the app's first run. (This is safe because the app
.apk is code signed, so the cert can not be modified.)
All of this should be handled automatically by Android's SSL libraries. If you are getting exceptions about not trusting the server's certificate, then try adding the root CA cert to the Android trust store.
Inventing your own method of establishing trust by having the server send a decryption key is almost certainly wrong, and is almost certainly more work.
For more reading, please see:
How does SSL/TLS work?
(I know it's a lot of text, but it is a very good reference)