The connection will time-out if you don't send something to the browser every once in a while. I like to just send out a space after every e-mail or every batch of e-mails. This keeps both apache and your browser from timing out. This of course won't work if you have output buffering turned on.
I would also send them out in about 10 e-mail batches instead of individually. This is quicker than starting sendmail for every e-mail address.
Also, make sure you change the PHP timeout (I think it defaults to like 30 seconds, but whoever installed PHP could have changed that to any value). I set my php.ini file to timeout after only 5 seconds, so I have to increase this for any PHP file that I know will take longer than that.
An alternative is to running it on the web, you could also run the script on your shell. I tend to prefer doing this for long-running scripts.
Bob