I solved the problem.
The way I did it, python didn't receive the name of the script to run (that is in the PATH_TRANSLATED environment variable). It seems that php can automatically extract the path from that variable and run the script, but not python.
So I wrote a small launcher script; htaccess points to this script.
AddHandler mypython .py
Action mypython /cgi-bin/runpython.cgi
and runpython.cgi contains: