For those interested in metasploit (or whatever) payload injection into EXE files, the metasploit patch (now posted http://www.metasploit.com/redmine/projects/framework/repository/revisions/8896) is based on one case, albeit the most likely to work, of my original program in C and Win32 API.
This original program also can embed the payload if it fits into unused space at the end of a code section, which it tries first. This can infect even weird or UPX'd EXE's, like some installers are, without unpacking them first and is a less suspicious modification of the executable; more likely to bypass AV's. It also can take advantage of an already-present import for CreateThread, which is smaller and less suspicious and adds the correct checksum to the file. (also less suspicious) However, the payload is not copied to an RWX page first, so no self-modifying encoders are allowed. This was done to make it more likely to fit into unused space, which usually only gives us 200-500 bytes.
Word of usability warning: Since this is a proof of concept, I just hardcoded it to look for raw shellcode in the file "payload.raw" and infects the executable "input.exe" saving its output in "output.exe". Feel free to modify that to make it more friendly.