O seguinte artigo da Wikipedia lhe dará uma dica: link
Basicamente, o que você precisa fazer (já que não pode controlar as tags) é adicionar algum tipo de espaço reservado para facilitar a substituição de texto com sed / awk / whatever.
Apenas preste atenção que esses arquivos estão compactados (melhor descrito como Nota de Aplicação Info-ZIP 970311, 1997) e você provavelmente precisará descompactá-los ou zcat-los para processá-los e zip-los de volta uma vez feito.