C'est effectivement avec l'url rewriting que tu dois faire ça.
PHP ne pourra pas y faire grand chose.

Sur du mutualisé, ça dépend de ton hébergeur.
Mais tu devras utiliser les fichiers .htaccess...