Após um pouco de teste & erro eu descobri. Os encantamentos mágicos são
RewriteEngine on
RewriteRule ^(.*)\.php5$ $1.php [H=application/x-httpd-php,PT]
RewriteRule ^(.*)\.php4$ $1.php [H=php4,PT]
onde application/x-httpd-php
é o manipulador padrão que mod_php5 registra, e php4
é um manipulador cgi customizado que chama php4. A parte que eu tive mais dificuldade em descobrir é a flag PT
(passthrough), que é necessária para que os manipuladores cgi funcionem. O PT faz com que outros módulos que fazem a regravação de url também façam seu trabalho, e o mod_cgi é um desses módulos.