From my admittedly hazy memories, a suitable donor cartridge (ISTR something like "Roger Clemens MVP Baseball" being a popular one about fifteen years ago), EPROMs (either electrically-erasable or UV-erasable) with a suitably close pinout, a couple of sockets, some solder wick (or you could use a suction device), some solder, and possibly some wire. Tools include a soldering iron, possibly a suction device such as a sold-a-pult, a pair of cutters so that you can clip the leads to the ROMs so that you can remove them one at a time after getting the chip package itself out of the way, the funky screwdriver that you need to open the cartridge in the first place... Probably others as well.
If you're going to go this route, you might check out
http://nesdev.com/, as they would have more of the hardware information available.