Is it possible to change/add the icon of an app without submitting a new binary?
Solution 1:
No, you cannot do this without resubmitting the app.
However, you do not actually need to rebuild the app using Xcode, as you otherwise indicate. If you look at the application bundle, you find the icons are usually stored in Contents/Resources/.icns. You can edit that file to change the icon. There's no need to rebuild the actual app executable.
If you're working with a signed app, you'll need to run the codesign program to resign the app.