An alternative way of generating non dictionary passwords is to use letters from a given phrase that the user can remember.

A trivial example. Given the phrase Any sufficiently advanced technology is indistinguishable from magic (Arthur C. Clarke) you can make a password "Asatiifm," which is easy to remember, once you know the catchphrase. You can make the method a little bit more complicated, by instructing users to use the last letter from every odd word, and the number of letters for every even one. So the password could be "y12d10s17m5," again easy to remember from the above schema.

Don't expect the users to learn these kind of passwords on the spot, though. Some training is needed, but after a few lessons, they should be able to cope with the problem without forgetting the password and without being tempted to write it down.

Or you can borrow the idea in this article and implement some more complicated mechanism. More security, but more training needed. Your call.