¿Cómo puedo reinstalar OS X sin una conexión válida al App Store?

¡He resuelto el problema!

Como dije, por alguna razón, no pude hacer funcionar el modo de recuperación (Cmd + R). Tampoco pude conectarme a la tienda de aplicaciones para (re)descargar el SO.

Sin embargo, tenía otro Mac. Así que utilicé el otro sistema para descargar El Capitán, instalarlo en una unidad flash, que utilicé para borrar el sistema "problemático" y reinstalar el SO.

He seguido estas instrucciones: https://support.apple.com/en-us/HT201372

Dos pasos importantes:

1. Mi primer intento falló porque mi unidad flash no estaba particionada con la opción de tabla de partición "GUID". Volver a particionar con esta opción activada solucionó el problema.
2. Para erradicar por completo el malware, formateé la unidad interna antes de instalar el SO (para asegurarme de que se realizaba una instalación completamente nueva en lugar de una mera actualización).

Todo funciona de maravilla. Esperemos que algo de esto ayude a alguien más por ahí. Gracias a todos por sus aportaciones.