If you want to destroy OutputDebugString -> Just patch a retn 4 at the begining of this API.

Else follow Param1 and put 0x00 there. Then just execute OutputDebugString.

Both Methods should fix vulnerability of Olly.

You better just patch if the machine is Win2k/2k3/XP. On Win 9x/ME every application shares its system-dlls with every other process afaik.

When to patch: I think it's the best to patch at EP.
Where to patch: Kernel32.dll and other System-DLLs on runtime.
How to patch: Maybe just put a JMP <to your code> in every API that needs to get modified. You may use VirtualAlloc to get some free space to put your code somewhere. Just execute it on EP, put your code to handle APIs to new allocated space, put your JMPs in the APIs and then restore EP and jump back.