The GNU sed manual
says "GNU sed has no built-in limit on line length; as long as it can malloc() more (virtual) memory, you can feed or construct lines as long as you like."
Also, the cut
command can be used with -b to specify locations by the byte offset.
I have also used emacs
to edit binary files, so it should work interactively. Just be sure to put it in fundamental mode (M-x fundamental-mode) not text mode so it doesn't wrap.