Про дебиан не могу сказать точно, но в убунте readline решлось просто:
apt-get install php5-readline
Стоит php 5.5.
Проблем никаких не было… видимо каноникал как-то решил эту проблему :) либо в одном из моих репо было это расширение.
Убунту основано на тестируемой, то есть следующей версии дебиана. Как я говорил, в ней php5-readline вернули. Данный способ же относится к текущей стабильной.
Поддержка интерактивной консоли PHP под Debian Linux