Safely deriving site-specific passwords from a master password is possible. It requires, namely, a deterministic one-way function: "deterministic" so that the site password can be recomputed, "one-way" so that it is not feasible to recompute the master password from a site-specific password. As first order approximation, a cryptographic hash function does the trick.
The system can be enhanced by making the password derivation (from master to site-specific) configurably slow, to avoid an efficient dictionary attack (an evil site could "try" potential master passwords, to see if it gets the one you used). A "slow hash" is a hash with many iterations. You may also add a salt: a piece of data which is not secret, but yet chosen randomly so that two distinct users of your master-to-site-password software do not end up with the same site password if they happen to use the master password. Salts can be stored in a file (they are not secret) but this would prevent you from rebuilding all your site-specific passwords from your knowledge of the master password alone (i.e. to the problem of remembering, you are adding the problem of data backup).
This is very similar to the question of storing server-side password hashes (for which the usual solutions are bcrypt and PBKDF2). The problem is made easier by the master password being "master". Since you have to remember only one password, you may as well make it a big, fat, random, high-entropy password. Generate a sequence of 17 random lowercase letters, learn it, and you will be fine (because 2617 is about 280, and invoking 280 times a hash function is beyond what is feasible with current technology). An all-lowercase letter password is easy to type, especially on smartphones.
Others have given pointers to existing software which does just that.
Your idea of using a RSA key and encrypted random passwords also works. However, it means storage. If you are traveling and someone steals your laptop (an unfortunate but alas not utterly implausible event), then not only are you deprived from your machine, but you also lost your passwords, until you buy a new machine and retrieve your backup of the encrypted file full of passwords. This can be inconvenient. Deriving the passwords deterministically from the master password means that you will not lose them while you remember the master password.
Also, any new password (for a new site) requires fiddling with the file and its backups, there again something which might be difficult while traveling.
Using an intermediary storage allows for password renewal, but why would you do that anyway ? Password renewal is useful when you manage a big organization with hundreds of passwords and you assume that some passwords will be weak, and some will be broken. It is a way of containing damage and makes sense only if there is a non-zero proportion of broken passwords at all times. Password renewal is a field army thing. It does not scale down: when you get down to a single master password (your case), that password is either fully not broken or fully broken. In the former case, there is no need to renew the master password; in the latter, you have more urgent issues to deal with, including changing all your previous site-specific passwords.
To state it briefly: if your master password needs renewal, then it was broken; which means then all your site passwords are toast. Thus, master password renewal without changing the site passwords is useless.