Other than education and pushing them to use a secure password manager, I'm not sure, but the solution shouldn't involve breaking existing and secure systems which are widely used even if only by a minority of users.
The proposed solution adds little to no real world security (see my other post about how easy it would be to guess which part is the random one which makes this system not useful unless almost all sites use it, which will never happen). Given little to no real world security gain from the described system, it certainly isn't worth breaking an existing system that works just fine and securely even if for just a minority of people.
Find a way to push for challenge-response authentication with a token that can be put onto a USB key. No, it's not easy to change the infrastructure to handle it, but IMO, it's the best chance to have secure authentication.
"This USB key is your identity card." is a simple concept to understand, and better than a password.