Buy your own domain, attach it to Fastmail (or use your direct @fastmail address if you don't want to own the domain). Then have Fastmail IMAP fetch the mails from your gmail addresses.

Create a filter that shows you which mails come from gmail-sourced accounts and go through it every once a while, visit those sites and change the addresses. It's a slow process but that way you won't lose any important emails.

I think my Gmail address is used by one store that refuses to give users the option of changing the email :D And they have loyalty bonuses that carry over between years so I can't be bothered to create a new account.

Previously I was getting by fine with a pre-paid LG flip phone and buying around $100/yr of minutes/service from TracFone.