He separado tu pregunta del tema para mantener el orden por allí.
Mi respuesta es que sí, lo soportan.
Por ejemplo, yo tengo una cuenta en Valcato Hosting que tiene soporte para Python pero es un alojamiento compartido, por lo que no tengo permisos de administrador en el servidor y por lo tanto no puedo instalarle nada.
Incluso ellos no tienen virtualenv en el path normal. Pero como solamente hace falta python para tener un entorno virtual, me descargué en mi cuenta el paquete de virtualenv y lo ejecuté. Un entorno virtual tiene disponibles easy_install y pip, y usarlo para un sitio es solamente cuestión de agregarlo con addsitedir en el archivo de fastcgi (escribí un pequeño tutorial sobre esto en mi blog:
http://blog.elcodiguero.com/2010/12/...alenv-fastcgi/
En definitiva: si tienen python y te permiten crear carpetas, podés instalar tantos paquetes como quieras gracias a virtualenv. La excepción podrían ser aquellos paquetes que necesitan compilarse, como PIL, pero al menos éste suele estar disponible.
Saludos.