Si el proveedor no sabe si tiene python instalado, apuesto una a mil a que no lo tiene.
Hay codigos y/o software que tienen requerimientos menos complicados para generarte un sitemap.
por ejemplo:
http://www.hotscripts.com/search/6455362.html Nota: Google esta escrito en buena medida en Python, pero me parece un desproposito (incluso un abuso o una burla) que pretendan que los webmasters lo installen en el server tan solo para generar los sitemaps!!!