How do I insert (not overwrite) a byte in hexl-mode?

You might prefer nhexl-mode, which lets you edit the file as if it was not hexlified (basically, the hexlification in nhexl-mode is done on-the-fly during redisplay), so you can insert/remove text without any difficulty.