A very easy scheme could be:

    password = hmac(url++nonce, master_key)

You then store url and nonce. it's no problem that this info is public as far as I know, but perhaps you could again encrypt both the URL and the Nonce using symmetric encryption using the master key

Every time you need to change your password, (because it leaked), you simply generate a new nonce. You only store the nonce and the URL and this seems like a very secure scheme to me.

Cons: You can not change the master key after the fact, so make sure it's secure.

I'm not a cryptographer, so I'm probably missing something obvious

Edit:

We still need to solve the "password constraints" problem. I would say, we could add functions that given the password stored, deterministically creates a string from the password that adheres to some specific password scheme. For example, by using the password as a seed to a random number generator used to fuel traditional password generators like the one included in lastpass. The 'scheme' would also be stored next to the nonce and the url.