Failed to connect to your database server. The server reports the following message: SQLSTATE[HY000] [2000] mysqlnd cannot connect to MySQL 4.1+ using the old insecure authentication.

Failed to connect to your database server. The server reports the following message: SQLSTATE[HY000] [2000] mysqlnd cannot connect to MySQL 4.1+ using the old insecure authentication. Please use an administration tool to reset your password with the command SET PASSWORD = PASSWORD('your_existing_password'). This will store a new, and more secure, hash value in mysql.user. If this user is used in other scripts executed by PHP 5.2 or earlier you might need to remove the old-passwords flag from your my.cnf file.

For a D7 site in my case, there is a setting in my webhosting Parallel Servobox Control Panel, a MySQL password hash length setting in password setting. Toggling it from: "Short, compatible with all PHP versions" to "Long, PHP5.x-only" fixed the issue and installation proceeded.

Prior also, I had to change the host setting from "localhost" to "127.0.0.1" to proceed with the database installation step. This might help for those needing to change the host in settings.php for already installed sites.