Puedes usar Mysql 4.1.x sobre cualquier versión de PHP. Tambien puedes usar las extensiones mysql (no es obligatorio usar mysqli pero si recomendable para obtener más beneficios:
www.php.net/mysqli) para conectarte a Mysql 4.1.x; lo que obtendras si lo haces así será un error tipo:
Cita: Warning: mysql_connect(): Client does not support authentication protocol requested by server; consider upgrading MySQL client...
Eso se produce por qué Mysql 4.1.x no gestiona igual los usuarios de Mysql vs a las versiones anteriores (desde 4.1.x de Msyql son encritadas las contraseñas de los usuarios) .. En definitiva, puedes usar igualmente esta versión de Mysql pero convirtiendo los usuarios a viejo estilo de gestión de contraseñas:
http://dev.mysql.com/doc/mysql/en/Old_client.html
Un saludo,