Is it possible to change/add the icon of an app without submitting a new binary? I had created a build with a friend's Mac, which I no longer have access to. Now, the last hurdle I have to overcome before my app is released is to create a unique app icon, but I'm not sure if you can do this without a Mac to create a new binary. Is it possible to do this from App Store Connect alone?
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.