In realtà potresti giocare un po con le funzioni fseek (che sposta la posizione corrente all'interno di un file) e ftruncate (che ridimensiona il file ad una dimensione specificata).

Ovviamente devi comunque giocare con dei buffer supplementari, e parte del file va comunque riscritto. Nel tuo caso, potresti leggere in un buffer a partire dal primo byte dopo il testo che vuoi eliminare, poi posizionarti sul primo byte del testo da eliminare e riscrivere sopra il buffer.
Infine troncare il file per eliminare i byte eccedenti.

Ovviamente ti risparmia solo in parte la riscrittura del file...