The "file full of passwords" is fine but requires some care when using it. When I travel with mine, I encrypt it with GnuPG and I decrypt it only on a portable computer (mine, so it is "clean") which runs Linux, without any swap space activated, and I decrypt only in /tmp, which I have configured as a "memory file system" (tmpfs) backed with RAM. The point of the exercise being to prevent any of my precious passwords to ever hit unencrypted a permanent data storage (the internal hard disk / SSD).
Some password manager applications (e.g. KeePass) can automate this process and give you an easier-to-use system.
Another method is to switch to mathematics at the time of generation of the passwords. The idea is to store in your mind a single "master password" (make it big and very random; say 20 random letters). When you need to generate a password for some usage U, then simply apply some deterministic cryptographic operation (say, hashing) which involves both U and the master password. "U" here will be a string using a format (any format that you wish) which somehow encodes the destination of the password.
For instance, make U the string "ssh:foo.example.com" to mean "the password used to connect with SSH to the machine foo.example.com". The encoding does not matter much as long as it is unambiguous, i.e. you can dynamically rebuild the string from your knowledge of the situation ("I want to connect with SSH to foo.example.com") and you won't have collisions (two distinct usages which end up on the same usage string).
The "cryptographic operation" which combines the master password and the usage string into a password must be designed with some care. I suggest using PBKDF2, the usage string U being the "salt". The iteration count for PBKDF2 is a trade-off: a higher count protects your master password better, but implies a higher cost when you want to recompute a password. An iteration cost of about one million is probably adequate.
I don't have a handy reference to an existing product which does that, but I am sure such products exists; and it could otherwise be reimplemented easily with a simple .NET application (.NET has an implementation of PBKDF2 since .NET 2.0 and it is also available on the Linux port Mono).
The point of using mathematics is that you don't have anything to store: the application (public, fixed) and the master password (private, never stored anywhere but in your head) conceptually "contain" all the passwords for a virtually infinite number of usages. Challenges with that kind of solution are:
You need to encode the PBKDF2 output (a sequence of bytes) into a "password" which will be considered acceptable "everywhere". Unfortunately, every site, server or application which accepts passwords can have its own restrictions (minimum length, maximum length, set of acceptable characters, set of NOT acceptable characters...) and it is unclear whether you can design a single encoding resulting in passwords which work for every system.
For the same destination (our "usage string"), you always get the same password. Some sites / systems force password changes on a regular basis (for no really rational reason, but that's humans for you). You can support such things by including the current date (month and year) in the "usage string", but it is cumbersome to have to remember whether a given site needs such rotating passwords or not.
So while this method has some elegance, it may be impractical until some heavy thinking and tinkering is invested in the creation of a product which does the job (the product can be a command-line tool with a short code).
Edit: as for your update, once you can store passwords, you can always encrypt arbitrary files with GnuPG (symmetric encryption with a password: gpg -c). Thus, you can store anything that way, including private keys for certificates.
