Con php se puede hacer, simplemente haces:
<?php
// consultas a base de datos para obtener la información que te construye las url
echo '<urlset xmlns="
http://www.sitemaps.org/schemas/sitemap/0.9" xmlns:xsi="
http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="
http://www.sitemaps.org/schemas/sitemap/0.9 http://www.sitemaps.org/schemas/sitemap/0.9/sitemap.xsd">';
// A partir de aquí puedes meter cada registro manualmente o recorriendo las consultas con while
// Ejemplo de forma manual, aunque dentro del while puede ir igual pero cambiando los datos por los generados desde las consultas:
echo
'<url>
<loc>URL</loc>
<lastmod>FECHA</lastmod>
<changefreq>daily</changefreq>
<priority>1.0</priority>
</url>';
echo '</urlset>';
?>
// después en htaccess pones que cuando se realice un búsqueda de /sitemap.xml te muestre la página de sitemap.php
RewriteRule ^sitemap.xml$ sitemap.php
