It's not hard to remember a different, strong password for every website

Let's take it as a given that it's a good idea to have a long password with upper case, lower case, numerals and special characters. Let's take it as a given that it's a good idea to have a different password for every website, and the main reason people don't is because it's very difficult to keep track of them all, and too much mental effort every time you need to sign in.

Your choices are:

1. Use the same password for every site and hope nobody hacks it, and then uses it on all your other websites.
2. Use a password wallet service and hope they never get hacked (NOT a given!), or nobody finds out the one password you use to sign in to it. 
3. Find a way to have a different password for every site.

I choose #3. You don't need to memorize 500 passwords; you need to memorize one set of rules that allows you to easily mentally calculate your password each time. Here is one example; I use one just like it, except totally different.

1. Memorize a list corresponding to letters of the alphabet

This may seem daunting, but it's surprisingly easy. Within a week, you're able to recall them instantly with no problem; it would be hard to remember 26 random words, but alphabetizing them fools the brain into giving them structure, and structure is easy to memorize.

Our example:
aardvark, bear, camel, duck, elephant, fox, giraffe, hamster, etc...

2. Transform them so they are not complete words

xkcd notwithstanding, it's not a good idea to use complete words, because one hacking strategy is dictionary-based. There are many ways you could transform them, swap out some letters for others, remove all vowels, truncate them to the second vowel; in our case, we'll just take the first three letters so it's easy to follow.

aar, bea, cam, duc, ele, fox, gir, ham...

3. Replace letters in the target website

Use a non-obvious pattern. In this case, we'll take the first four letters of the website, but in reverse order. Our example website will be cabernet.com (it doens't exist... yet), so the letters are e-b-a-c and our code is now:

elebeaaarcam

4. Add some rules for capitalization, numbers and special characters.

The sky's the limit here, we already have a pretty good password, so you can limit the complexity of these rules so they're easy to implement quickly. For our example, we'll:

1. capitalize the first and last consonant
2. right in the middle, add 858 if the website ends in .com, 636 for any other TLD (I just took the easily remembered 747 and shifted it up or down a digit)
3. at the end of the word, add %$# (that's the special characters above 543) if the website name begins with a vowel, #$% (the same, reversed) if it begins with a consonant.

So our example is now:

eLebea858arcaM#$%

This scores 100% on passwordstrength.com, and most importantly, if a hacker finds it out due to a vulnerability on a website you're signed up for, and over which you have no control, they don't now have all your passwords or an easy way of figuring them out.

This is a bit of mental effort, traded for a lot of security. And it's a lot less mental effort than it seems; the human brain is really good at remembering and implementing repetitive rules. My algorithm is somewhat more complicated than this example, and I never have to hesitate more than a second or two, and I always gets it right.