En términos generales hay varias opciones:
1. Llevarlo a Android 6 con una ROM modificada (Cyanogenmod, LineageOS...)
donde ya no va a tener problemas.
2. Rootear e instalar una app o una combinación de ellas para modificar el
country code _cu a _us para que la tarjeta de red permita la conexión.
No dices modelo exacto, S4 hay unos 30 modelos entre el modelo base, el Mini,
el Zoom, y el Active.
Para cada modelo el rooteo varía pero es bastante simple de hacer con Odín si
es un fichero para flashear o con alguna de esas app para rootear.