If you buy your phone unlocked, you can get Red Pocket which is extremely cheap for service compared to most post paid plans. You can get ~5gb data and unlimited everything else for 20 a month on AT&T. And then if you go to Europe you can just buy a cheap Sim while there and pop it in.
If you're not picky about the phone, I have gotten sub 300 USD phones for the last 2, first lasted 4 years and I'm about 6 months into the second. Honestly there's not much I feel like I'm missing, except spending way more money.