Just a suggestion - not tested but hope something here might help.
You need to store current and old passwords somewhere as you are going to check that they've not re-used them. Can you use this object as the source for confirming that they have entered the correct current password? Not sure if you can store the old passwords as HashStrings, and then compare hashStrings?
Do not show the real password element of your change password form - have 2 extra password attributes and only update the real password field after they have passed your tests. Hopefully you will be able to see the 'dummy' password attributes in your microflows
HTH
BTW, a password management module would be a useful addition to the apps store
@Andrew To check the passwords, you need to use a java action, which uses the systemcontext to compare the two hashes. The same action could be used to check whether an password has been used before.
The password strength validation i am not sure about, did you try to inherit an entity for system.user and than add an additional validation rule with a regex?
@David We indeed planned to add an account management module to the appstore.