My answer is kind of two parts.
The first is that generally, you're best off making mods for games that have a high level of support for mod making. Sometimes this stuff can be extremely involved and frankly you want all the help you can get.
Maybe there was a crack team out there that was able to decompile a game and insert their own assets. More likely they got help from the developers and access to their utilities.
Even if you do have those kind of abilities? It's a whole lot easier when someone has built tools for you.
That out of the way, I would suggest looking at the Unreal Development Kit.
Turns out someone really has made the tools for you.
I'm not really sure how to elaborate on this other than to say it's probably far beyond what you need. There's a LOT of material out there on the UDK. A lot of things you can read. And a lot of tutorials.
The development team I'm with is using it ourselves and while I can't speak for everyone I'm finding it to be excellent.
I've been working with it for about two weeks now, and not too long ago I was able to make a rocket launcher that fire rockets that when it exploded left a fire behind. A fire which both spread in a line, and dealt damage to anything close by.
Lasers that bounce off walls, cloaking devices? Pretty easy to make a mod for UT3 that includes things like that. Killer Robot Monkey that chases after enemies and breathes swarms of bees at your enemies shouldn't be too hard to program either.
It's kind of only really limited by imagination and performance issues. We're expecting to be able to make a pretty good burning down buildings system going.
I'm currently working on a stealth system. Enemies won't see you if you're in dark areas.
I only mention all of the above to give you an idea of what's feasible (which is a lot). There might be a better game and better tools for making mods, but the UDK is probably one of the best. And the fact of the matter is that again, there is a lot of documentation. It's a big part of why we chose it.