I've been using HMAC-SHA1 as a basis for my passwords for awhile. I call my algorithm "Passy". It works like this (pseudocode'ish).

    # generate our HMAC
    hash = generate HMAC-SHA1 (facebook.com, passphrase) (String)
    hash += SHA1(hash) # just need the extra length
    
    # transform hash into a Passy
    passy_chars = "ABCDEFGHabcdefgh23456789#$%*+=@?"
    passy = ""
    foreach octet in hash (starting with MSB)
      passy += passy_chars[octet % 32]

    # figure out the length of this passy
    for i in 16 to passy.length
      if passy.substr(0,i) is "good", return passy.substr(0,i)
        where good means includes at least one from each of [A-H], [a-h], [2-9], and [#$%*+=@?]

I've implemented this in CoffeeScript, and have a minified version up here: http://dl.dropbox.com/u/11596/passy-tiny.html

I have evolved this algorithm over the past decade. My requirements:

  1. minimum of 80 bits of entropy (16*32=80)
  2. must include at least one symbol, one uppercase, one lowercase, and one digit
  3. base it on cryptographically secure hash algorithms
  4. avoids confusing similar symbols O and 0, l and 1 and !, etc.

I realize that requirement #2 does nothing to increase entropy. It's simply there to satisfy (idiotic!) password requirements.

With any of these systems, your generates passwords are still only as good as a) the strength of your passphrase, and b) the secrecy of your passphrase. As well as the obvious (physical security, keyboard sniffers, etc.)