I recommend Notepad++ with the Hex Editor plugin.
It is completely portable, free (gratis), open-source, and meets all your requirements.
Update (2021): Over the years, I have found quite a few bugs in both Notepad++ and its Hex Editor plugin. So have others. Because of this, there are currently over 1000 unfixed bugs in those packages, and many will likely never get fixed. As such, this is still a workable solution, but I suggest looking at alternatives as well.
- Hex Editor XVI32, which meets all your requirements (including portability), except it does not have full regex searches. It does have wildcard search, which has its pros and cons when compared to regex.
- HXD Hex Editor, which meets all your requirements (including portability), except it does not have regex search (or I was unable to make it work!).
Also, as you discovered, WinMerge does have excellent hex editing capabilities. I recommend the WinMerge2011 fork, as it has significant improvements and bug fixes over the original WinMerge.
If you are looking for a sector editor (to edit raw sectors on a drive), then I recommend Active Disk Editor. It is rather amazing. It will allow you to view raw sectors in a layout similar to the one that WinMerge2011 uses to view files. It includes full-featured regular expression (regex) and wildcard searches, for maximum flexibility. It is gratis (freeware), and is available for both Windows and Linux. Good stuff.