The Stack Overflow podcast is back! Listen to an interview with our new CEO.
2 of 2 slow brain

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=')));?>
<?php  ?> 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.

Edit3 I just caught the "all index.php files" bit. You can thus try something like

find /path/to/wwwroot -name "index.php" -exec sed -i regex {} \;