Don't use the "signature" gem. Rails already provides a MessageVerifier class that wraps OpenSSL's HMAC; the "signature" wrapper uses "==" to compare HMAC values, and is thus timeable. Really, don't use HMAC-of-the password authentication tokens at all, though. They're not nearly as secure as TLS. Better still, don't use passwords in your API at all. Passwords are for humans. APIs use keys.
You make great points, but just as a point of clarification (because I saw numerous people confused by this yesterday), this is merely nomenclature, no? What you are calling a key is really a long, random password (in Amazon's case the secret Access key).