We're off to see the wizard, the wonderful Wizard of Woz
We hear he is a whiz of a wiz, if ever a wiz there was
If ever, oh ever a wiz there was, The Wizard of Woz is one because
Because, because, because, because, because
Because of the wonderful things he does
We're off to see the wizard, the wonderful Wizard of Woz

...is that I'm really hungry for gyros!

Given that your minimum requirements are 1) having different passwords for each site, and 2) changing them once a month, it's probably a good idea to have an algorithm that allows you to come up with your password. The algorithm could take the name of the company/website and the current month (or month & year....something time-related) as inputs, do "something" with them (jumble, transpose, use your Little Orphan Annie Secret Decoder Ring, etc) to get your password. You can also factor in rules for putting numbers, symbols, uppercase, etc. It just has to be consistent. Now all you have to do is protect the algorithm, not the individual passwords. The algorithm can be written down and put in a safe deposit box.

Using an algorithm can eliminate the need to write down passwords, unless your algorithm is so convoluted that you can't calculate it in your head. If you suspect that your algorithm has been compromised, just change it. Granted, websites have varying requirements (some take symbols, some don't), so it's not perfect.