The 27C040 should be fine. I used a 27C4001 but they should be the same.
As for an eprom programmer, I have no idea what to recommend. I've heard bad things about the clone Willems on eBay, but I've also heard that they work well enough. The biggest drawback is that you have to have a parallel port on your PC to use it. The USB to parallel port adapters designed for use with printers will NOT work. You can power it with USB or AC, I don't think it matters. But make no mistake: the USB is not for data transfer, only power.
The linked tool will work fine. Get the rom, apply the patch, then run it through the utility to get your PRG (or CHR? I can't remember. Only one file will have anything, the other will be 0kb.). You can burn the .PRG directly, it's already in binary format so no need to make it a .bin.
Here's a thread here where I explained a bit about what I used: viewtopic.php?f=28&t=12811
Note that the eprom is a drop in replacement. No need to bend any pins. The best way to get the old rom out if you don't have a desoldering iron is to cut all the legs off the chip, then head the remaining pin and push it through so it falls out. It will totally ruin the chip obviously, but trying to get it out in one piece will probably ruin your board too. Then use a desoldering braid to clean up any excess solder in the holes. It's a little tricky.
I'm also open to selling my copy if you're interested. I just don't really play it that much.