For reference, I am the author of Easy Passwords extension which uses a very similar concept.
These issues are definitely solvable, at least if you use a hybrid concept: while most passwords are generated, some can be encrypted and stored (encryption key derived from the master password). Easy Passwords has this functionality and LessPass appears to be working on it as well. Then changing algorithm or master password can be done by converting all existing generated passwords into stored password. This isn't a great solution of course and so far I haven't seen the need to implement this escape hatch but it can be done if absolutely necessary.
As to remembering the websites where you registered - that should definitely be the job of the extension (not storing passwords doesn't mean that you cannot store metadata). And many password generators support a revision counter for passwords, you increase it when you need a new password.
These issues are definitely solvable, at least if you use a hybrid concept: while most passwords are generated, some can be encrypted and stored (encryption key derived from the master password). Easy Passwords has this functionality and LessPass appears to be working on it as well. Then changing algorithm or master password can be done by converting all existing generated passwords into stored password. This isn't a great solution of course and so far I haven't seen the need to implement this escape hatch but it can be done if absolutely necessary.
As to remembering the websites where you registered - that should definitely be the job of the extension (not storing passwords doesn't mean that you cannot store metadata). And many password generators support a revision counter for passwords, you increase it when you need a new password.