How to prevent username and password matches when changing a username?

The only sensible way to get what you want is to ask for the password when a user changes their username. This way the server always has the information needed to conduct an accurate comparison between the username and password during a change, and prevent matches.

As sensitive operations - such as changing passwords, or in your case usernames - should require a password anyways (to limit the damage of XSS), this shouldn't be a problem.

Your only other alternative is to try every possible case combination, hash it, and compare that to the stored hash when a user changes their username.

Going against the grain a little - don't care whether the username is changed to a "substantially similar" string as the password. Warn users about the danger of selecting the same password and check for the identical match.

No matter how many rules you put in place, if the user is determined they'll find a way around them. If you must, prompt for the password upon username change so you can force them to the same casing, or just let it through and check the next time they log in and force a user/pass change then.

The only time any of this matters is if your users are subjected to a targeted attack. If a random script kiddie (or some other opportunist) gets ahold of the user list, they have way more sophisticated tools to break those passwords than trying to match the username. So does the targeted attacker, for that matter, but they may start with simple things they can type into the keyboard themselves. And if it's an intelligent person trying to break the password "PwdRsch1", are you really going to be safe just checking case differences? What about "pwdr5ch1"? "PwdRsch2"? "1hcsRdwP"? You can write rules for any of these scenarios you can think of, but either there'll be one you forgot or you'll make it so difficult to select a username/password combo that they'll just wind up using "P4ssw0rd!" and be done with it.

Education is the only way to get your users to use genuinely secure passwords, and there will always be those that don't comply.

Let's say the username has 10 letters in it. That's 1024 different combinations of upper and lower case. Check them all.

Don't store the lower case password hash. That 1024 may seem inconvenient to you, but it's the difference between a day and three years for a attacker.