CreateProcess the victim with CREATE_SUSPENDED, do whatever code patching, then ResumeThread it. Pretty sure you can even CreateRemoteThread into the victim for DLL injection, since it just suspends the primary thread, and then patch "yourself" in DllMain instead of having to do remote memory calls.
Selfish question for a project of my own: is there any way to magically gain early code execution in a process on Windows other than a shim DLL? I'm too lazy to write one to pass through the all exports (reflective shim DLL possible...?)