You do not need to decompile the binary. If you understand what changes you want to make, and those changes can be made by only modifying the binary file or its dependencies, then you can just make those modifications on disk or in memory.
You have a few choices on how to effect the modification itself.
You could use LD_PRELOAD to have the linker load a shared object before the binary runs. Then you don't need to modify the binary on disk at all. This is kind of what valgrind does, it loads as a shared object but then begins dynamic binary instrumentation.
You could use valgrind. Valgrind would allow you to dynamically re-write the program and modify its behavior arbitrarily. Valgrind is a dynamic binary instrumentation program that allows its tools to edit the program while it executes. If you just want to change program behavior this might work, but valgrind also incurs a global slowdown and if you wanted to patch and redistribute a program, it probably is not ideal.
You could also use tools like elfsh/eresi to insert new code into the program. Those tools should take care of the act of injecting your code with relation to stuff like the ELF program header. There is a concept of "ELF infector" that you could google for, where your injected code becomes the new program entry point, does something, then jumps to the old program entry point.
