here is what i think would be a good way of doing it.
you would have your domain as domain.com
any member that signs up, will have a directory.
no you have a choice, to actually have a directory or not.
in your .htaccess file you can actually have it so if that directory is not there, it will redirect to your redirect script which then will manage everything..
eg.
domain.com/someUser/
.htaccess redirects to
domain.com/redir.php?user=someUser
then u can do loggin and do the actual redirect to their site.
or you can actually create the directoy, probably a little bit easier and less complicated... so u don't have to have about 1,000,000 lines in ur .htaccess file of code.
but then ur stuck with 1,000,000 directories.
inside the directory create a file called index.phtml
it will log whatever you want and then redirect the user. You can even opt to put a pop-up banner to make some money.
my only suggestion is, that you don't create a million directories in ur public_html directory, create it in a sub directory or subdomain, eg
domain.com/redir/someUser/
or
redir.domain.com/someUser/
hope that gives you some idea on how you want to achieve this.