My problem is that I have included all media inside my main exe. The exe is getting quite big over the time (4 MB).
Is it possible to write an exe file updater, so I don't need to "replace" the whole exe file, instead only make/apply the changes needed inside the exe file itself?
Another option (if you mainly expect to update media, levels, etc.) is to add some logic in your .EXE to check an external config file that may point to alternative external media/levels/whatever that can override the existing incbin'ed copies.
e.g. load incbin::whatever.jpg unless external file whatever2.jpg exists, then use it.