Assumung you don't use these tricks anywhere, why not this (appropriately executed, using
sed -i and maybe
find -exec ..., which was not part of your question, was it?)
$ sed 's/eval(gzuncompress(base64_decode(.*)));//' << EOF > <?php eval(gzuncompress(base64_decode('eF5Tcffxd3L0CY5WjzcyNDGGMV4+1dSwqSqzU0LQGAJCPCMM=')));eval(gzuncompress(base64_decode('eF5LK81LLsnMzKx+JjNW0rgUAqDUUxQ=='))); eval(gzuncompress(base64_decode('eF6VlMmy/3sMxOez/iJOojHFT0Ig/8jlTymmN/I=')));?> > EOF <?php ?>
...you can afterwards deal with the empty
<?php ?>s (which don't hurt much, do they?).
Edit removed line breaks to make sure it fits to the situation described.
Edit2 You'd be better off just replacing everything with a (known good) backup, probably, if you've got one.