Simple, you just have two pages, one for username change and one for email change.

The user has to enter their email and the desired new username or email.

The server hashes the email they entered with SHA1 and compares with database. If it matches, it sends an email to the plain-text email they submitted to the server. If the user clicks the link sent to them, it confirms username or email change.