The keystore and its password are used to sign the app that is then used by Android to identify the developer. If leaked, someone could update the concerned app on our behalf. Even if the person doesn't have access to our playstore account, they still could publish it somewhere else.
We see everywhere, "never lose it", "never leak it", etc. But what if I did? I cannot find the required steps to follow when they both, the keystore and its password, leak so I can protect our users and our app.
Even if I publish the same app with an other appid, how can I protect my users that are still on the old one? Is there some best practice here?
Unfortunately there doesn't seem to be a great way to migrate an existing application to a new signing key. This is probably for the best, since the best practice remains to a) have a strong key and b) keep your private release key as private as possible. I found this article outlining a feasible (but rather user un-friendly way) to migrate from a 1024 bit to a 4096 bit key, which seems to fit your use case. Since you still have a valid signing key for the compromised app, you can attempt to migrate them away from it via update.