Choose a complex base password + a memorizable _algorithm_ that combines (eg) domain names with the base password. That satisfies all of your requirements, and it's not super difficult to create an algorithm that is easy to perform mentally and hard to reverse.
I started doing this in college, and it's been super easy to keep up and my passwords are pretty secure.