It looks like you have overseen the very beginning...
Taifun
Note:
Please see this solution by @Anke. Thank you Anke.
Note: According to Mr. Pratim, the process ddescribed below is outdated. The package name now can be changed by:
- Using apktool 2.1.1 decompile the apk, edit it and recompile it.
- Getting a pem certificate and pk8 key with OpenSSL.
- Signing the apk.
Mr. Pratim described this process in detail here. Thank you!
See also this guide by Avram. Thank you!