You can technically distribute patches, a good example of what is possible is SNES ROM hacks, where only the deltas are be distributed, and the end-user provides their own 'legal' copy; this avoids the issue of redistributing copyrighted content.

However in the EU you aren't allowed to use information obtained through "decompilation" for the purpose development/production of a substantially similar program. Which means you cannot patch any program (exception exists for the purpose of interoperability), without risking some legal liability.

2009/24/EC Article 6 for anyone interested.