楼上提到签名轮换的倒是好心，但是没审题，题主是要换包名，不是换签名。

我的建议是你们把新版本的 apk ，打到老版本去，出一个老版本的更新，这个更新安装之后，首次打开就把新版本装上，startActivity ，然后 finish 自己。新版本打开之后去引导用户把老版本卸载，从此只更新新版本。我们公司有个项目就是这么干的。

代价自然是用户的体验、操作成本，还有部分反感，不过这也是没有办法的办法，你们可以提前几个版本，邮件或者挂 banner 通知用户你们打算这么做。

有些人可能会问，既然都通知用户了，为啥不直接引导用户自己去下新版本？我想说真正待过几个项目的应该都知道，用户（尤其海外的）小白起来是非常小白的，没有人会跟着你一步步去下新版，安装，再卸旧版，只能尽可能自己做更多，让他们少做。