La mejor opción (la única opción hasta donde yo sé) es Root + safestrap.
Detalles: Samsung bloqueó sus cargadores de arranque - El acceso al cargador de arranque es necesario para escribir un nuevo software operativo (análogo a la instalación de Windows).
Safestrap es una forma de aislar diferentes programas de Operrating; y ejecutarlos sin desbloquearlos.
Así que..: Si quieres Lollipop Tendrás que Rootear tu teléfono, instalar SafeStrap, y luego adquirir una Rom LP.
Término de búsqueda en Google: Root Safestrap Galaxy S4 versión actual aquí PD: Haga siempre una copia de seguridad de sus datos antes de iniciar este proceso. Sus mensajes de texto no guardados se perderán.