I know this is somewhat common knowledge and can be found elsewhere, but it's just so awesome that I have to repost it. I had always used xxd to generate a listing, edited that listing with vim, and then used xxd -r to re-create the binary file. Instead, you can use vim to open the binary file, shell out to xxd using the current buffer as input, modify the binary content by editing the hex digits (that's right, no need to edit the ascii, that's just for show,) and then shell out to xxd with the current buffer again to get the binary representation.
Once more for posterity...
vim -b binaryfile
Edit the hex column in the center.
Save the file and it's patched.
For some extra goodness (prettier columns):
So, that was pretty cool, but also check out :help xxd. Vim's built-in help has a nice bit of code to put in your .vimrc and then vim -b will automatically handle shelling out to xxd when you open a binary file and then shell out to xxd when you save the modified buffer.