Could you not load the entire file in to memory (eg: membanks) and then just look up the bits you need, make changes if required and write back the changes at the end when you are done? It would probably be much quicker and the amounts of RAM on desktop's devices is not so limited as it used to. Even if you planned to run on a GP2X, you've got quite a few Mb's to play with.
BTW, is it Cave Story you'll be editing by any chance
BTW, is it Cave Story you'll be editing by any chance