You could setup imapsync and sync your Gmail to a self hosted IMAP server and just never delete your mails.