The above mentioned solution does not work if you want to install the new application side by side with the old.

Suppose you have an oldapk.apk and you want to rename its package from com.oldcompany.oldname to com.mycompany.myname and install the newapk.apk side by side with the oldapk.apk, follow these steps:

1. Install apktoolgui: https://github.com/AndnixSH/APKToolGUI

2. Install ruplacer: https://github.com/dmerejkowsky/ruplacer

3. Decompile apk using apktoolgui

4. Edit oldapk/apktool.yml:

   - renameManifestPackage: null
   + renameManifestPackage: com.mycompany.myname

5. Replace old names to new:

   ruplacer "Lcom/oldcompany/oldname" "Lcom/mycompany/myname"
   ruplacer "com\.oldcompany\.oldname" "com.mycompany.myname"

6. Run ruplacer afterwards again with option --go (first run was only reporting)

7. Rename folders smali(...)/com/oldcompany/oldname to smali/com/mycompany/myname

8. Compile newapk.apk (including align/sign) using apktoolgui