You don't check on every request to see if the password has changed, you check to see that the session is valid on every request. You should be doing that anyways.
Then all you have to add is a way for password changes to invalidate the session.
The thing is that the way that a session is usually "validated" these days is to just store a userid in some serialized format then encrypt that and send it off as a cookie that expires in a relatively short amount of time (and hopefully put the expire time in the encrypted message too). Then the server just has to try to decrypt the cookie and if it results in a valid userid then the session is valid. This way you don't cause an extra database request for every user request.
I'm not saying it's good or secure, but it's the way I often see it done/suggested to be done.
Then all you have to add is a way for password changes to invalidate the session.