I tried more than 10 approaches and none of them worked (and sometimes not explained completely, so I deviated a little and found my own way. Again, my way is also not simple, but it does the job and Google Play didn't give me any errors.
My Solution
1. On the Project pane on the left, select Project (it might say Android).
2. Go to nameOfYourProject -> app ->src -> main ->java ->com -> example
3. Right click on "example" -> Refactor -> Rename and type your desired name, select the two check boxes and hit Refactor.
4. Now go one level above example (folder) and right click on "com", but this time DO NOT check the two check boxes (as it will also rename the "com.google...." parts of your project) and hit Refactor.
5. Now open your Manifist file and manually change the package to your desired name.
6. Rebuild your project. If you see any errors, just open the file with the error and change the package name manually.
7. Open your gradle.build file and change application ID, to your new package (only the parts of it, not everything) and hit Sync (top right side). Hopefully this works.
P.S. Another "easy way" might be to use Agent Ransack, search for the package name by enclosing it with quotations and manually change the package name. You might want to get a copy of your project before doing this. I didn't try it, cause I was already knee-deep with all the other methods here and didn't try.