Der Präsident zieht in Erwägung:
1. Gegen einen letztinstanzlichen kantonalen Entscheid betreffend die Verweigerung der bedingten Entlassung aus einer Massnahme ist die Beschwerde in Strafsachen an das Bundesgericht gegeben (<ref-law>). In deren Rahmen kann auch die Verletzung verfassungsmässiger Rechte geltend gemacht werden. Die als staatsrechtliche Beschwerde bezeichnete Eingabe ist folglich als Beschwerde im Sinne von <ref-law> entgegenzunehmen.
Wie sich aus der Rechtsmittelbelehrung des angefochtenen Entscheids ergibt, ist dagegen ein kantonaler Rekurs möglich. Der angefochtene Entscheid ist somit nicht letztinstanzlich im Sinne von <ref-law>. Dass der Beschwerdeführer die Rechtsmittelbelehrung des angefochtenen Entscheids beachten sollte, ist ihm im Übrigen seit dem Urteil 6A.108/2008 vom 11. Dezember 2006, welches ebenfalls die Verweigerung einer bedingten Entlassung betraf, bekannt (E. 2). Auf die Beschwerde ist im Verfahren nach <ref-law> nicht einzutreten.
2. Die Gerichtskosten sind dem Beschwerdeführer aufzuerlegen (<ref-law>). Das Gesuch um unentgeltliche Rechtspflege ist in Anwendung von <ref-law> abzuweisen, weil die Rechtsbegehren aussichtslos erschienen. Der finanziellen Lage des Beschwerdeführers ist durch eine herabgesetzte Gerichtsgebühr Rechnung zu tragen.

Demnach erkennt der Präsident:
1. Auf die Beschwerde wird nicht eingetreten.
2. Das Gesuch um unentgeltliche Rechtspflege wird abgewiesen.
3. Die Gerichtskosten von Fr. 500.-- werden dem Beschwerdeführer auferlegt.
4. Dieses Urteil wird den Parteien und dem Amt für Justizvollzug des Kantons Basel-Stadt, Strafvollzug, schriftlich mitgeteilt.
Lausanne, 26. Februar 2009
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Favre Monn