Подскажите как правильно пропатчить exe если необходимо в него добавить свой код, который не вмещается на месте оригинального. Например, я хочу добавить некую процедуру - как ее вcтавить в уже готовый exe гарантировано не нарушив его работоспособность.

Обычно в концах секций есть свободное место, если нет - добавить свою. Многие PE-редакторы это умеют.

Пиши свой код в dll, дальше прицепи эту длл к импрорту проги, а в DllMain() патчи нужное место в проге на вызов функции из длл. Дешево и сердито - я часто так делаю.

LordPE прекрасно справляется с добавлением новой секции,
советую его. А вот небезызвестную утилиту ToPo мой Kaspersky,
с последними обновл. базами, признал почему-то вирусом "ToPo". :-)

Воспользуйся OllyDbg'oм - он позволяет добавлять код также просто, как если бы ты писал обычный исходник. К тому же есть функция отмены/добавления кода (изменения кусков кода можно включать/отключать в окне Patch). Кроме этого он позволяет проверить код на работоспособность (на то он и Debugger) и если все проходит нормально - сохранить его в EXE. При этом нет необходимости помнить, по каким адресам расположены измененные куски кода, т.к. OllyDbg позволяет сохранить сразу все изменения в файл. Единственный недостаток - он не изменяет PE-заголовок, поэтому придется его править ручками, или использовать уже имеющиеся функции.

Кстати совсем забыл - сохраняй значения регистров, которые были до твоего кода и потом восстанавливай их, т.к. регистры очень часто содержат жизненно важную для проги инфу и ее нарушение приводит к краху программы или даже системы.
Хотя я думаю ты сам об этом все знаешь ;-)

Смотря куда - если в самое начало(в смысле кода, а не фаила :)), то ищи в PE заголовке EntryPoint и прописывай туды все, что хочешь...