TL;DR: How do you know it's not the attacker who is changing the password? In that case, you would log out the legitimate user. Or a user might want to routinely change their password (a good practice), but not if they have to login again on all devices every time. I would only log all other sessions out if (1) the user clicks the button "log all other sessions out", or (2) the user uses the forgot-password feature (thereby confirming their email address, or something else which provides stronger proof that it's them than a password).
When to log all other sessions out?
There are a few cases in which a user's password gets changed:
- User notices or suspects a compromise, and changes their password
- Attacker just gained access to an account and changes the user's password
- User forgot their password
- Attacker compromised user's email account and uses the forgot-password feature
- User routinely changes their password, either because they think it improves security or because of a policy
In each case, you would want to make a different choice, but it's impossible to distinguish between the legitimate user and an attacker. Since you can hardly ask the user to confirm their password when using the forgot-password feature, we have to either disregard the case where an attacker compromised a user's email account, or use another method of confirming the user's identity (e.g. a recent purchase, an SMS verification code, a security question, etc.).
Since we do not know who is changing the password when it is changed from the interface, I think it's not unreasonable to leave other sessions active. In that case, other sessions should be terminated when a user does a password reset (after they confirmed the password reset link, not whenever anyone enters their email into the form, because that could be abused). Imagine the scenario in which both are logged in and know the password: both will try to change the password (assuming they know of each other) and it's just luck who gets there first. But once the password reset feature has been used successfully by someone, you have a higher confidence that this is the legitimate user.
Another consideration is whether to have a separate interface for logging other sessions out: you could have a button for "Log out all other sesssions", perhaps next to a list of all other sessions and past logins. I would recommend having this, since a user can check what is going on when something strange happens to their account. An attacker will be unable to hide their presence.
How to manage the sessions?
Ideally, you should have a list of active sessions for any account, as well as a history of logins. The history of logins should date back a certain amount of time, not a certain number of logins: if only the last X logins are shown, an attacker will be sure to look in the account history, spoof the user agent and country/state/city using VPN, and do X logins to push his own login out of memory.
This can be managed in a database, where each login session is registered. Using a
expires column, you can purge sessions which have expired. And a session should get removed upon log out of course. Note that this is separate from login logging: having logged out, it should still be visible that someone logged into the account using <device> from <location> on <datetime>. The only thing to remove (or the boolean to toggle) is that the session is active.
Doing some trickery with bcrypt-hashed passwords, as described in the question, is not needed (and definitely not recommended!). The session state should be independent from a user's password by design: otherwise session tokens have a meaning which could be guessed if you make some tiny mistake, even if the attacker doesn't really know the password. Or conversely, an attacker could learn the password through offline brute-force, when all they ever obtained was a session token.
Generally speaking, there should be a list of sessions with at least two columns: session token and the user's unique identifier. The session token should be random bytes, optionally hashed (in order to not leak data from a compromised or weak PRNG). The user's unique identifier should be stable: no display name, and preferably not a username. Use a single-use unique identifier, such as an auto-incrementing column in MariaDB/MySQL. Usually a third column is added, expiration time, but this is not strictly necessary. I would highly recommend it, though, even if you set it to multiple years.
For each request, the database can be checked for the presence of the session token. If a user does something that invalidates other sessions, it's a simple matter to inactivate (or delete) the user's other sessions.
 Do not use security questions as a replacement for a password. The only reason I dare mention it, is because it can be an addition: when the user confirmed a secret code (or link) sent to their email account, or when they proved that they know their password, you could use it to get a little more certainty that it's the real user and not an attacker.