>   It does for auto-revert-mode (everything seems to work fine), however
> with auto-revert-tail-mode it's even more broken. When I append to a
> file externally and both auto-revert-tail-mode and hexl-mode are
> activated, first emacs tells me:
> "Converting to hexl format discards undo info; ok? (y or n)",
> and when I answer "yes" the buffer fills with gibberish.

Sorry, my attempt was too simplistic.  Please try again with the
attached patch.  I think something better is needed, but an
important first step would be to test whether revert-buffer works
correctly whenever the file changes.