A py2exe generated executable basically consists of three main parts - PYTHONSCRIPT, the runtime python dll & library.zip.
PYTHONSCRIPT can be modified with a decent resource editor. It is basically a marshalled array holding pyc files. The main script of the application is usually stored here.
In order to make changes you need to unmarshal the code objects, decompile it to py, make changes, recompile back to pyc, marshal it back to generate a new PYTHONSCRIPT and finally update the executable.
Modifying library.zip is easier as it is a standard zip file. It contains other pyc/pyo files. You can decompile them, make changes, recompile it back to pyc/pyo, and zip them up. Next replace the overlay in the executable with your new zip file and you are done.
In order to automate some of the above steps you can use a tool Py2Exe Binary Editor
Note: I am the author of the above tool