You users table will need a verified field that is set to either 0 or 1.
On update you will need to store the old email address (possibly in session variable or hidden field).
When the user changes their email address you will need to create an email (possibly using UE) and Update behaviour to update and then custom code the trigger to make it compare the old email address to the new. The email would contain a link to a page that lookups the email address and then sets the verified field to 1.
Also, add a second update behaviour which sets the verified field to 0, again custom code the trigger to make it compare the old email address to the new.
You will probably also need to change your login script to make sure that the value of the verified field is equal to 1.
Hope this helps.
Cheers
Ian