Удалить байты из файла без его полной перезаписи можно только с конца?
Вы можете не перезаписывать весь файл, а только кусок с хвоста, который останется после удаления из середины данных. Для обрезания размера файла с конца в современных ОС есть соответствующие механизмы.
Если же вам нужно удалить в большом файле несколько байт в начале, то придется перезаписать весь файл.
Для того что бы не перезаписывать большие объемы информации многие файлы внутри имеют блочную структуру (например файлы баз данных), тогда можно помечать весь блок как удаленный, при этом сам блок из файла не освобождается и не перезаписывается, но приложение знает, что он пустой и его можно будет повторно использовать при необходимости. Этот функционал вы должны сами запрограммировать в своем приложении - операционная система за вас это не сделает. При этом когда злобный админ будет делать shrink базы данных эти пустые блоки будут физически удалены из базы. 
Блочная запись на диск и copy-on-write - это все верно, но находится на уровне дискового драйвера (а copy-on-write - это вообще даже не драйвер, а прошивка контроллера диска). При этом дисковый драйвер и контроллер диска ничего не знают про файлы, они работают с секторами, блоками и т.п.
Пользовательская программа, работая с файлами, обычно, не опускается на такой низкий уровень, а потому не может управлять подобными операциями.
Вообще это  зависит  от файловой системы.
В  большинстве известных  систем без разницы -  хоть с начала, хоть с конца удаляйте, никто файл полностью перезаписывать не будет.
То же самое и с добавлением - можете добавить хоть гигабайт в середину файла. 
Сам файл зачем трогать?
В основном принцип такой- 
Запись на диск идет блоками фиксированного размера - кластерами.
Это минимальная адресуемая единица файловой системы, размер кластера может быть разным, чаще всего 4килобайта.
Вы поменяли часть файла - на диск в любое свободное место будут записаны кластеры которые изменились. В базе данных файловой системы изменятся координаты расположения файла.