If you're on apache, you can add the following to the top-level .htaccess file:

ErrorDocument 404 /404.cgi
[download]

That will internally redirect any non-found requests to /404.cgi. 404.cgi can then figure out what the original request was by examining $ENV{REQUEST_URI} and show the appropriate information (i.e a valid user page, or a 404 not found page)

In my experience, this works on lots of shared hosting solutions even if mod_rewrite isn't available.