I do not use Linux so my suggestion could be hopelessly wrong.

Could your executable not create the icon in the correct directory(ies) on first run? So the executable starts up, checks in the directory for the icon file, if it does not find it, creates/copies it and carries on.

As part of your install process/instructions you could just execute the program once to create the icons.