I have used the Verizon S4 on T-Mobile prepaid before i sneaked onto a Verizon plan,and voice/data/text were all fully functional, so i can confirm that works with that GSM band--
the S4 contains radio support for frequencies (and please correct me if i'm mistaken):
LTE 750 / 1700
WCDMA 850 / 1900 / 2100
CDMA 850 / 1900
GSM 850 / 900 / 1800 / 1900
so confirm with a rep from whichever company (even if an MVNO, just check their website) what bands in particular they use for their network.
you'll receive a pop-up in the notification tray stating "Non-Verizon SIM", but you'll still have complete functionality. the only way to remove that pesky notification is to root the phone, and go into a hidden menu that Samsung/Verizon hid.
from what i have read, it should also be usable on any GSM network (att)--your overall signal strength will vary depending on the carrier's footprint in your area. ATT was great for me in South Carolina, while T-Mobile was absolutely horrendous.
that's my .02c