Clearly it works best if the request to update a password happens as a response to an inbound request to access a known system, but how do you make an outbound request to users to update their passwords?
Technical half: changing the password
The simple and secure way is a round-about, "You don't."
When a user logs in with their old password, display a notice saying they must reset their password. Generate an email with a reset token and send it to their email address. The email address token must be used because we no longer trust the password (and we hope that the email address is still under a users' control).
Human half: discussing a breach
If you're requesting users update their passwords, it may be because you're changing hashing algorithms. That really should happen behind the scenes, or involve reclaiming old accounts rather than leaving them dormant. It probably is because you've encountered a breach, though.
Breaches affect customers even if you don't hold any sensitive information because online presences are often linked (same username, email address, etc.) and because passwords are often re-used. If you've lost control of your password database, users may be at risk of having those passwords brute-forced and then used against accounts from other sites.
Regardless of your motivation, the technical method of changing passwords remains the same. If you've had a breach, though, disclosing that is important for your ethical duty to your users and sometimes for legal requirements depending on your jurisdiction. How the letter is written is a combination entirely of legal and subjective matters, but it should explain why users may need to be concerned about other accounts and why they need to reset their password on their next login.
Obviously, if you want to send a request to users (without waiting for them to come back), then you have to contact them in some way, which, most of the time, means sending emails. This works only if you know of a valid email address for each user (which is a good reason for verifying the email address when the user first registers).
Thanks to spammers and other villains with fraudulent intentions, typical users are trained to disregard emails which talk about passwords. This is your biggest problem. Similarly, you do not really want to reverse that training. So it would be bad practice to send an email with a clickable link to a password reset page: the security-aware users will not follow the link, and the others just so demonstrate how vulnerable they are.
Let's try another way. Usually, when you need users to do a mass-reset of the passwords, it is because it is suspected, for some contextual reason, that a substantial number of user passwords may be compromised. For instance, someone broke into your server and grabbed a copy of the database of hashed passwords.
Compromised passwords are an issue because they allow unauthorized reentry. Conversely, compromised passwords are not an issue (at least, not for your server) until the attacker tries to come back. This means that you can, somehow, wait. Technically, this involves the following:
- You configure your server so that every successful login is redirected to a password reset page (I assume a Web server here). The user is not permitted to access any other service before the password is reset.
- The "password reset page" is actually a pre-reset page: the user can click on a button, which makes the server send him (by mail) a transient, user-specific link to the true password reset page.
- The true password reset page, as its name says, allows the user the reset his password.
- Optionally, you proactively send an email to every user to warn them about the issue, and to courteously (but firmly) suggest that they should reset their password in the near future. No clickable link, please !
This setup is "secure" as long as we assume that the attacker did not guess a user's password and compromised the user's email at the same time.
The relevance of sending a mass email depends on the situation: it may be good for public relations ("see, we are taking security seriously, and we do not want to hide the issues") and it can be bad for public relations ("we got hacked, it is embarrassing"). The current zeitgeist is that, on a general basis, the email should be sent; denying issues has a high probability of making them only worse. Admit your misfortune, eat your hat, and beg for forgiveness -- users will forgive you if they feel that you treat them "fairly" (i.e. you use a lot of flattery). Also, as you indicate, users tend to reuse passwords, so while this is not technically your problem, a proactive warning will be felt as a positive gesture.
If your server is big enough, hire a public relations specialist right away, to handle the crisis.
About your only option, if you don't want to wait for your users' next login, is to send your users an email and ask them to log in. That's a bit dubious: your users may delete the email as spam/phishing.
Alternatively, you can disable every user account on your site, and the next time they log in, require them to go through some special extra process to authenticate themselves. In addition to requiring them to provide their password, you might also require them to solve a CAPTCHA or ask them some questions about their account activity (e.g., for an email provider, ask them to provide the email addresses of a few correspondents that the user regularly contacts). Or, you might perform some other checks. None of this is ideal, but hey, you asked.