How can I add bytes to an existing file without:
As you have described it you're going to need operating-system support to do that
.
As far as I know this sort of thing is only easy for files stored on punched cards.
or if you can add a shim between the userspace and the filesystem.
The best you can hope to do in java is override the file reading an writing code your own application is using to fake the presence of the extra bytes.
I hope you're not trying to corrupt perfectly good text files by adding UTF-8 BOM to the start.