I recommend Notepad++ with the Hex Editor plugin.
It is completely portable, free (gratis), open-source, meets all your requirements, and is high-quality.
- 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.