It's actually not as hard as it seems. Just set up forwarding from gmail to your new email address, then update your email everywhere at your leisure.