Hex Fiend is a freeware (BSD-licensed) hex editor that can handle data insertion and editing on arbitrarily-sized files:
Rui Carmo