I suppose you have two options:
search for some free, unused space in the executable, put your code
there, and put a JMP wherever you originally wanted to insert more
instructions. (this would probably involve changing the permissions so the code can be executed without access violations)
instead of static patching, inject a DLL and put a JMP to your code contained in the DLL.
In both cases, you'd need to preserve the program state
(probably a PUSHAD then POPAD when you're done), then JMP back
and resume execution.
An example (second approach, assuming MSVC):
void __declspec(naked) MyCode()
//your code here
__asm PUSH returnAddress
and to patch it:
DWORD AddrToPatch = 0xC0DE;
DWORD RelAddr = (DWORD)(MyCode - (DWORD)AddrToPatch) - 5;
*AddrToPatch = 0xE9;
*((DWORD *)(AddrToPatch + 0x1)) = RelAddr;
Honestly, I think you're better off doing it like that - the first method is a lot more hassle, and injecting a DLL is fairly easy, you can automate that by playing around with the IAT or TLS callbacks.