All that I did was follow the exact tutorial as mentioned on the Google Developers page to include GCM.
https://developers.google.com/cloud-messaging/android/client
Added all needed permissions at the manifest, gradle dependencies at app level and module level.
I even uninstalled the app, did a gradlew clean, re-build. Nothing works out. I get the same error INSTALL_PARSE_FAILED_NO_CERTIFICATES error.
When I revert back the changes, everything gets back to normal, I don't get any packaging or certificate error. Any help would be appreciated.