Although I am not really familiar with Android Development, I got it to work like this:

- decompile using apktool

- make changes

- recompile apk using apktool

- zipalign apk

- sign apk (using the apksigner.jar) with a certificate

Tools like uber-apk-signer really help to do the last three steps