> Did Amazon once offer free shipping to people who didn't have Prime?

Yes. It wasn't next day delivery. You still get it, but there's a minimum spend requirement now.

> I'm pretty sure that they can't just change the benefits of Prime in the middle of my membership.

Don't they have a clause saying they can change the terms whenever they like?