The problem for most mere mortals with the HMAC scheme is that there is a very real possibility of the server being compromised and the secret key being stolen. In this case an adversary could generate valid cookies for any user. However, with the magic number scheme as long as only the hash of the random number is stored (we should add a per-user salt too) then the entire session database could be compromised, but an attacker cannot do anything with it.
Also, though less of an issue with SSL, the HMAC approach is subject to replay attacks while expire_at < now.
EDIT: The HMAC approach also lacks any method to invalidate cookies manually, or automatically e.g. when the user changes their password. This means a compromised account is open to attack until expire_at < now, and there's nothing you can do about it other than blocking the account for that duration, which now means that each request needs to do a database lookup to see if the account is blocked. You could generate a per-user secret key, but now you have a database lookup again, so you might as well use the magic number scheme.
If your server is compromised you tend to have bigger problems than session forgery. Why would an attacker bother to fabricate http-sessions after he already gained access to your database and, in most cases, source-code?
Replay-attacks work the exact same whether you use this scheme or store a magic number server-side. There's no difference whatsoever.
For a password-change you update the last_logout timestamp and hand the user a new cookie (since his current one was just invalidated).