PBKDF2-SHA256+SHA256 for password storage
Thanks to @Stephen Touset for the solution.

In order to avoid tying the session cookie to the user's password (and avoid using PBKDF2-SHA256+SHA256), we can simply create a random $key$ for the user upon login. $SHA256(key)$ is then stored in the db, along with a session ID that ties the session to a specific user. 

$key$ is then used as the preimage in the session cookie. Upon each request, we calculate $SHA256(key)$, and compare it to the value stored in the db.