Exacto, no puedes hacer esto sin HTML, vaya ni si quiera sin Javascript (sí es posible pero te va a quedar muy complicado y enredado), pero al menos el HTML es necesario.
El lado de PHP ya te expliqué que tienes que hacer, es solamente contestar y generar el código adecuado, si no sabes como leer las variables en tu PHP es simple:
http://www.php.net/variables.external
Si te pidieron no usar HTML, pues dudo mucho que puedas hacer un select, ya que necesitas usar HTML para ello.
Saludos.