It is possible to make some changes to the APK yes, but it depends on how it was generated and signed. The APK format is nothing more than a ZIP file, when seen in a simple way.
You could, in some cases, change the icons manually using an application such as 7-Zip or WinRAR. However, I believe the simplest way to do this would be to use the APK Icon Editor .
Simply load APK into your application and use the Replacement options icon menu. The program has two modes of operation, the ZIP and the APK Tool . The first makes a simple replacement of the icon files (should solve your problem); the latter offers more advanced features, mostly related to reverse engineering. You can select them in the program settings.
EDIT: Another option is to use the APK Manager program. This tutorial of the XDA Developers Forum details the procedure.