binary sed replacement

Old question, but,

xxd infile | sed 's/xxxx xxxx/yyyy yyyy/' | xxd -r > outfile

is probably the simplest and most reliable solution. Similar to the edit in the OP.

bbe is a "sed for binary files", and should work more efficiently for large binary files than hexdumping/reconstructing.

An example of its use:

$ bbe -e 's/original/replaced/' infile > outfile

Further information on the man page.