Step 1: User changes email address.
Step 2: He clicks on a link to verify his new email address.
My question is simple: is he supposed to be logged in or not to verify his new email?
No. What you need to know is that the user has actually access to the e-mail account he claims to own, just that. It doesn't matter if the same user is logged in later or not.
Also, most users will be already logged on, since in order to change the e-mail address, they should have been logged on first.
Moreover, imagine the edge case: the user is using your web app on a device, but doesn't have (or don't want to) access to the e-mail account from this device. He uses another device to confirm the new e-mail address, but has no intention to log on from this other device.
Unrelated to UX: Technically, it's easier to not requiring log on before verification process. The first verification process (when the user registers for the first time) can't require the user to be logged on, since he can't: his account is not available until the verification process finishes. If you want to use most of the source code for the successive verification processes (when the user changes the e-mail address), don't require the user to be logged on neither.