I'm pretty happy with my Galaxy S4. If the Mini you're talking about is the S4 mini, and it's not too different from the S4, it's a solid phone.
Have you looked into used phones? I've been getting (completely useless to me as a foreigner) ads for Ting.com, which claim to offer lower rates than other providers. They've got a calculator that shows how much cheaper they are than everyone else, but everybody does. Why they might be interesting is that while they don't do $0 phones, they've got a market for used ones, so you could get an older smartphone model for under $100, which might give you a bigger selection to chose from. You also avoid the big caveat of $0 phones, which is that they usually come with much more expensive plans than the phones you pay for.
Even if you're stuck on Verizon, you might be able to buy a used phone and move the plan over, which means that you can change to a cheaper plan sooner. A used S3 could be a great money saver, and you still have a decent phone.
On the features - while removable storage is a plus, you generally only use it whenever you change phones. If you're mainly going to use that storage for stuff you're going to have copies of on your computer (music and pictures you take with the phone), storage that you can't remove isn't going to be a problem.
4G vs. 3G is kinda weird, since there's no real standard on what you can call 4G and 3G. From what I can see online, Verizon 4G is faster than Verizon 3G, but how that compares to the IPhone 3G isn't really clear. What is clear is that Verizon might throttle your 3G speed if you're a "heavy" user (over 2GB in a month), while that doesn't happen with 4G (see
here. If you're not going to be watching videos or streaming music to your phone, it's probably not going to make any difference to you whatsoever.
Moving music from ITunes to an IPhone is pretty easy, but it's going to be pretty easy to move the music to any droid phone. If you're just using ITunes to play mp3s, you're just going to have to copy the music files to your phone. If you've bought music through ITunes store that's one some kind of bullshit closed format (FairPlay), there's free programs out there that can convert those files to mp3 - that's going to take some hours of work, but I'd say it'd be worth it.
Battery life is probably what's going to be the biggest thing in your day-to-day life, and I consider that the most important point of everything you listed above. It's probably what should be the biggest influence on your purchasing plan.
