It is possible to make some changes to the APK yes, but that depends on how it was generated and signed. The APK format is nothing more than a ZIP file when viewed simply.
You could in some cases change the icons manually using an application like 7-Zip or Winrar. However, I believe the simplest way to do this would be to use the APK Icon Editor.
Simply load the APK into the application and in the Icon menu use the replacement options. The program has two operating modes, the ZIP and the APK Tool. The first makes a simple replacement of icon files (should solve your problem); the second offers more advanced features, mostly linked to reverse engineering. You can select them in the program settings.
EDIT: Another option is to use the APK Manager program. This tutorial XDA Developers Forum details the procedure.
The problem is to sign the APK, and not compile. But at this price you can pay the Google license, use the free tools and still have change.
– Bacco