This is the advice I give to my family members. The solution is to create a one-time-pad in excel(!) that contains all of your passwords. Store it on an encrypted thumb drive and carry it with your keys. There is the possiblity that your OTP may contain a character set that is not congruent with a web-service's password system, but these circumstances are rare.
I don't know about Linux, but I've been using KeePassX for Mac for about a year now. It only supports the older KeePass file format, and it's ugly, but it works great. There are also a few iOS apps you can use, my favorite of which is KyPass.
