.htaccess içerisinde
ErrorDocument 404 yonlendir.php

gibi bir satır olacak tabi öncesinde yine yapman gereken şeyler var. (wildcard DNS gibi)

www.milliscripts.com ile bunu biraz uğraşarak yapabilirsin.