Few years ago, as a school project I have written hed. It’s yet another terminal hexadecimal editor, but with few unique features.
Thanks to its splay tree file representation, it is able to very efficiently handle editing and even inserting to huge files; the file is not loaded in memory as a whole, just the modified parts are saved, and therefore you are able to edit even files many gigabytes in size efficiently. You can also save just the swap file separately as a “working diff” and restore your changes later on top of unmodified original file.
It uses vi-like keybindings (including marks and yank/paste registers or :!). It also features an “expression” concept that lets you efficiently compose search, substitute or jump expressions composed from a variety of data representations, supporting arithmetic operators and register references. E.g. using special register “. (data under cursor), you can use command #”. to jump to file offset written under cursor.
I’m writing about it again now since I just pushed out Debian packaging for the editor, so you can easily make Debian or Ubuntu packages for yourself from the source (it also has existing OpenSUSE packaging). Try it out! I’m not maintaining the project anymore, but Petr Tesarik will gladly accept any patches or feedback (or I will too, forwarding it to him :-).