I think it would be simpler and easier to remember one password to your non-cloud based password program such as Keepass. That way, you can create not only random passwords, but random usernames (since usernames are one key to unlocking your account).

The disadvantage of this approach is that your more restricted on where you can login to services (since you'll need your password manager there, and a trusted computer to run it on).