Many sites send a mail to the specified email address containing a randomly generated verification code and only accept the user registration once the user has confirmed they were able to read that mail and obtain the verification code. Usually the mail contains an URL that the user can simply click to confirm.
If you do that, all you need to do is make the confirmation email instead tell the user that they've already registered and explain the password reset procedure.
Whatever web development framework probably has a package that handles confirmation mails.
Note that you have to think about the case where a user had an email address and used it to register to your site, then they vanished without changing the address and stopped using the address, and another user now has the address and wants to register. There's no easy answer here.
ADDED: You add that you don't want a confirmation email so that the registration proceeds immediately. This requirement is contradictory with unique email addresses, because you don't know that the email address supplied by the user is legitimate until it's been confirmed, and there's no point in enforcing the uniqueness of a user-chosen string that just happens to be formatted like an email address (if you want a unique user name, it doesn't need to be formatted like an email address).
If you want to keep instant registration, you'll have to treat email addresses as just an untrusted text field until confirmed. That means that every action that requires your site to send a mail must bomb out if the user hasn't confirm his email address. The confirmation process remains pretty much the same, but now, if the address is a duplicate, the user must either be given the option to merge the two accounts (which sound difficult), or told that he must close one of the two accounts or change the email address associated with one of the two accounts.