I have a database that stores a user's access token (along with some other data). My list of permissions include offline_access when I authorize the user.
So will the user's access token (client side) always be the same as that user's access token in the database? Or can the user's access token change when they log out, change their password, etc?
No, the access token will not always be the same, even with offline_access. You will need to get a new access token when 1) the user changes their password or 2) deactivates your app. Otherwise, it should remain the same.
The users Facebook id will never change though. This can be parsed from the access token or obtained by calling the /me graph api.
Facebook has a blog post that goes on in detail about this.
Update: Facebook added a blog post specifically for handling revoked authorization.