it doesn't have to be complicated. if you implement a token concept like i described in Is your web application really secure? ("CSRF") you have that technique for all actions. implement once, use it everywhere.
about users having forgot their password and don't have access to their email address - well, i would expire the permanent cookie after a certain time. a permanent cookie means comfort, but if you have to login after, say, two months again, that's not that bad... forgetting passwords should not be encouraged.
and to send an email with an approval link to the new and the old email address is a very common practice.