Sachverhalt:
A. X._ befindet sich seit 1988 im Massnahmenvollzug. Er wurde gestützt auf die Urteile des Appellationsgerichts des Kantons Basel-Stadt vom 4. März 1988 und des Kantonsgerichts St. Gallen vom 21. November 1995 im Sinne von Art. 42 aStGB verwahrt. Infolge der Revision des Allgemeinen Teils des Strafgesetzbuches wurde die Verwahrung von X._ überprüft und am 8. Januar 2008 in eine stationäre Massnahme nach Art. 59 Abs. 1 und 3 StGB überführt.
B. Die Vollzugsbehörde (Ressort Strafvollzug des Amtes für Justizvollzug) verweigerte am 11. Februar 2009 die bedingte Entlassung von X._. Auf den Rekurs des Betroffenen trat das Justiz- und Sicherheitsdepartement des Kantons Basel-Stadt am 11. Mai 2009 nicht ein. X._ rekurierte an den Regierungsrat des Kantons Basel-Stadt. Der Rekurs wurde dem Appellationsgericht des Kantons Basel-Stadt (als Verwaltungsgericht) am 10. Juni 2009 als Sprungrekurs überwiesen. Mit Urteil vom 16. September 2009 bestätigte dieses den Entscheid der Vollzugsbehörde vom 11. Februar 2009.
X._ führt Beschwerde beim Bundesgericht. Er beantragt im Wesentlichen die Aufhebung des angefochtenen Entscheids des Appellationsgerichts. Überdies ersucht er um unentgeltliche Rechtspflege und Verbeiständung.
C. Das Appellationsgericht verzichtet am 29. Januar 2010 auf eine Vernehmlassung. Das Justiz- und Sicherheitsdepartement des Kantons Basel-Stadt schliesst in seiner Eingabe vom 17. Februar 2010 auf Abweisung der Beschwerde. Die Vollzugsbehörde hat sich innert Frist nicht vernehmen lassen.

Erwägungen:
1. Die als staatsrechtliche Beschwerde und Verwaltungsgerichtsbeschwerde bezeichneten Eingaben des Beschwerdeführers sind als Beschwerde in Strafsachen entgegenzunehmen (Art. 78 Abs. 2 lit. b BGG). Mit diesem Rechtsmittel können auch Verfassungsverletzungen gerügt werden.
2. Der Beschwerdeführer beklagt sich über ein verfassungswidriges Verfahren. Einerseits macht er sinngemäss geltend, auf die von ihm vorgetragene Befangenheitsrüge in Bezug auf Prof. med. A._ sei zu Unrecht nicht eingetreten bzw. diese sei willkürlich als unbegründet erachtet worden. Andererseits rügt er eine Verletzung des Anspruchs auf unentgeltliche Rechtsverbeiständung. Wiewohl er in jedem Verfahrensabschnitt um die Beigabe eines Rechtsbeistandes ersucht und auf die Notwendigkeit eines solchen zur Wahrung seiner Interessen hingewiesen habe, sei er ihm aus nicht nachvollziehbaren Gründen versagt worden.
2. Der Beschwerdeführer beklagt sich über ein verfassungswidriges Verfahren. Einerseits macht er sinngemäss geltend, auf die von ihm vorgetragene Befangenheitsrüge in Bezug auf Prof. med. A._ sei zu Unrecht nicht eingetreten bzw. diese sei willkürlich als unbegründet erachtet worden. Andererseits rügt er eine Verletzung des Anspruchs auf unentgeltliche Rechtsverbeiständung. Wiewohl er in jedem Verfahrensabschnitt um die Beigabe eines Rechtsbeistandes ersucht und auf die Notwendigkeit eines solchen zur Wahrung seiner Interessen hingewiesen habe, sei er ihm aus nicht nachvollziehbaren Gründen versagt worden.
2.1 2.1.1 Zur geltend gemachten Befangenheit von Prof. med. A._ führt die Vorinstanz im angefochtenen Entscheid aus, der Beschwerdeführer habe einen entsprechenden Antrag (auf Feststellung der Befangenheit bzw. auf Ausstand) erstmals im Verfahren vor ihr vorgebracht. Die Beanstandung sei damit verspätet, zumal Befangenheit unverzüglich bei ihrer Feststellung zu monieren sei. Der Beschwerdeführer könne nicht das Beurteilungsergebnis abwarten und dann im Rechtsmittelverfahren angebliche Befangenheit geltend machen, wenn ihm das Ergebnis der Untersuchung nicht entspreche. Ein solches Verhalten verstosse gegen Treu und Glauben. Im Übrigen sei die Rüge unbegründet. Der Rekurrent bringe gegenüber den Universitären Psychiatrischen Klinken Basel (UPK) resp. gegenüber Prof. med. A._ einzig vor, dass ihm das Ergebnis der medizinischen Untersuchung nicht zusage. Gründe, dass das Gutachten nicht wissenschaftlichen Anforderungen genügen würde, würden hingegen keine geltend gemacht. Hinzu komme, dass die Beanstandungen nicht konkrete Vorhaltungen, sondern bloss generelle Unmutsbekundungen darstellten (angefochtener Entscheid, S. 4 f.).
2.1.2 Nach Art. 30 Abs. 1 BV und Art. 6 Ziff. 1 EMRK hat jede Person Anspruch darauf, dass ihre Sache von einem unparteiischen, unvoreingenommenen und unbefangenen Richter entschieden wird. Nach der Rechtsprechung des Bundesgerichts wird diese Verfahrensgarantie sinngemäss auch auf das Erfordernis der Unabhängigkeit und Unparteilichkeit von Sachverständigen übertragen. Befangenheit ist anzunehmen, wenn Umstände vorliegen, die geeignet sind, Misstrauen in die Unparteilichkeit eines Sachverständigen zu erwecken. Dazu kann auch zählen, dass die sachverständige Person in einem früheren Zeitpunkt in amtlicher Funktion mit der konkreten Sache schon zu tun hatte (sog. Vorbefassung). Ablehnungsbegehren müssen so früh wie möglich gestellt werden. Wer eine sachverständige Person nicht unverzüglich ablehnt, wenn er vom Ablehnungsgrund Kenntnis erhält, verwirkt den Anspruch gemäss Art. 30 Abs. 1 BV (Urteil 6P.93/2001 des Bundesgerichts vom 17. Dezember 2002 in ZBl 105/2004 S. 206 ff., E. 1.1; vgl. <ref-ruling> E. 2b; <ref-ruling> E. 3c).
2.1.3 Der Entscheid, den Beschwerdeführer nicht aus der Massnahme zu entlassen, stützt sich auf das Gutachten der UPK vom 31. Oktober 2007, den Therapiebericht des Psychiatrisch Psychologischen Dienstes (PPD) Zürich vom 18. September 2008, den Bericht der Anstaltsleitung vom 2. Dezember 2008 sowie die Anhörung bzw. Empfehlung der Interkantonalen Fachkommission zur Beurteilung der Gemeingefährlichkeit (IFKGS) vom 17. November 2008. Wie sich aus den erwähnten Entscheidgrundlagen ergibt, wirkte Prof. med. A._ als ordentliches Kommissionsmitglied an der Empfehlung der IFKGS aktiv mit. Weiter ergibt sich, dass das Gutachten vom 31. Oktober 2007 von der Abteilung Forensische Psychiatrie der UPK erstellt wurde. Prof. med. A._ ist Leiter dieser Abteilung. Die Gutachtenserstellung erfolgte mithin, d.h. angesichts seiner leitenden Stellung, unter seiner Oberaufsicht. Dies war im Übrigen auch bereits bei der Gutachtenserstellung durch die UPK im Jahre 2002 der Fall, weshalb Prof. med. A._ in der Folge als Kommissionsmitglied der IFKGS im Hinblick auf die damals anstehende Beurteilung des Beschwerdeführers im Zusammenhang mit der bedingten Entlassung in den Ausstand trat. Davon abgesehen befasste sich Prof. med. A._ mit dem Beschwerdeführer auch im Jahre 1989.
2.1.4 Diese Gegebenheiten bzw. Ämter- oder Funktionenkumulation, worin der Beschwerdeführer in erster Linie die Befangenheit von Prof. med. A._ im Sinne einer unzulässigen Vorbefassung erblickt, ergeben sich - wenn auch laienhaft formuliert - aus dem Rekurs bzw. der Rekursbegründung vom 20./25. Mai 2009 an die Vorinstanz. Der Beschwerdeführer stellt darin denn auch explizit einen Antrag auf Feststellung der Befangenheit bzw. auf Ausstand von Prof. med. A._. Dass der Beschwerdeführer den Genannten - aus den nämlichen Gründen - für befangen hält, ergibt sich aber auch aus dem Rekurs bzw. der Rekursbegründung vom 16./21. Februar 2009 an das Justiz- und Sicherheitsdepartement (JSD) des Kantons Basel-Stadt. Davon geht auch die Vorinstanz aus. Sie weist im angefochtenen Entscheid darauf hin, dass der Beschwerdeführer seine Beanstandungen gegen Prof. med. A._ bereits im Rekurs an das JSD formulierte (angefochtener Entscheid, S. 7). Damit hat der Beschwerdeführer seine Bedenken gegen Prof. med. A._ aber unverzüglich im Sinne der Rechtsprechung von Art. 30 Abs. 1 BV geltend gemacht. Denn der Bericht der IFKGS vom 17. November 2008, aus dem sich die Mitglieder-Zusammensetzung der Kommission ergibt, wurde ihm erst nach dem Entscheid der Vollzugsbehörde vom 11. Februar 2009 zugestellt (angefochtener Entscheid S. 6). Auf die Befangenheitsrüge wegen Verspätung dennoch nicht eintreten zu wollen, weil der nicht anwaltlich vertretene Beschwerdeführer nur vor der Vorinstanz, nicht aber vor dem JSD ein förmliches Ausstandsbegehren in Bezug auf Prof. med. A._ stellte, erweist sich unter den geschilderten Umständen im Sinne von Art. 29 Abs. 1 BV als überspitzt formalistisch (<ref-ruling> E. 5; <ref-ruling> E. 5.4.1). Der angefochtene Entscheid hält damit vor der Verfassung nicht stand.
2.1.5 Soweit die Vorinstanz die Befangenheitsrüge im Übrigen für unbegründet hält, weil der Beschwerdeführer gegenüber Prof. med. A._ einzig vorbringe, dass ihm das Ergebnis der medizinischen Untersuchung nicht zusage, er aber keine Gründe geltend mache, dass das Gutachten nicht wissenschaftlichen Anforderungen genügen würde, erweist sich der angefochtene Entscheid als tatsachenwidrig und damit als willkürlich. Denn entgegen der vorinstanzlichen Feststellung wendet sich der Beschwerdeführer in seinem Rekurs vom 20./25. Mai 2009 nicht ausschliesslich gegen das medizinische Untersuchungsergebnis, sondern macht er vielmehr geltend, Prof. med. A._ sei vorbefasst, weil er mit ihm bereits im Jahre 1989 zu tun hatte, er als Leiter der UPK bei der Gutachtenserstellung 2002 und 2007 beteiligt war und als aktives Kommissionsmitglied an der IFKGS-Empfehlung im Jahre 2008 mitwirkte (vgl. Rekursbegründung Ziff. 5 und 6). Mit diesem Vorbringen setzt sich die Vorinstanz nicht auseinander. Soweit sie meint, der Beschwerdeführer hätte zur Erhebung einer begründeten Befangenheitsrüge zusätzlich die Wissenschaftlichkeit des Gutachtens in Zweifel ziehen müssen, ist ihrer Auffassung nicht zuzustimmen.
2.1.5 Soweit die Vorinstanz die Befangenheitsrüge im Übrigen für unbegründet hält, weil der Beschwerdeführer gegenüber Prof. med. A._ einzig vorbringe, dass ihm das Ergebnis der medizinischen Untersuchung nicht zusage, er aber keine Gründe geltend mache, dass das Gutachten nicht wissenschaftlichen Anforderungen genügen würde, erweist sich der angefochtene Entscheid als tatsachenwidrig und damit als willkürlich. Denn entgegen der vorinstanzlichen Feststellung wendet sich der Beschwerdeführer in seinem Rekurs vom 20./25. Mai 2009 nicht ausschliesslich gegen das medizinische Untersuchungsergebnis, sondern macht er vielmehr geltend, Prof. med. A._ sei vorbefasst, weil er mit ihm bereits im Jahre 1989 zu tun hatte, er als Leiter der UPK bei der Gutachtenserstellung 2002 und 2007 beteiligt war und als aktives Kommissionsmitglied an der IFKGS-Empfehlung im Jahre 2008 mitwirkte (vgl. Rekursbegründung Ziff. 5 und 6). Mit diesem Vorbringen setzt sich die Vorinstanz nicht auseinander. Soweit sie meint, der Beschwerdeführer hätte zur Erhebung einer begründeten Befangenheitsrüge zusätzlich die Wissenschaftlichkeit des Gutachtens in Zweifel ziehen müssen, ist ihrer Auffassung nicht zuzustimmen.
2.2 2.2.1 Zum Gesuch um unentgeltliche Rechtspflege und Verbeiständung führt die Vorinstanz aus, das JSD habe dem Beschwerdeführer zu Unrecht eine Spruchgebühr auferlegt, weil seine Mittellosigkeit nicht zweifelhaft erscheine und sein Rekurs aufgrund der mangelhaft durchgeführten Akteneinsicht nicht von vornherein aussichtslos gewesen sei. Im Verfahren vor ihr sei dem Antrag des Beschwerdeführers insofern entsprochen worden, als man auf die Erhebung eines Kostenvorschusses verzichtet habe. Da in diesem Verfahrensstadium die Rekursbegründung aber bereits erfolgt sei, habe anwaltlicher Beistand nicht mehr helfen können, da mit der Replik nichts Wesentliches mehr in das Verfahren habe bzw. hätte eingebracht werden können. Überdies sei es nicht Sache des Gerichts, dem Beschwerdeführer einen Anwalt zu suchen. Es bleibe daher dabei, dass der Beschwerdeführer sich selber vertreten habe und dass ihm für das Verfahren keine Gebühr auferlegt werde.
2.2.2 Nach Art. 6 Ziff. 3 lit. c EMRK und Art. 29 Abs. 3 BV hat eine bedürftige Partei, die nicht über die erforderlichen Mittel verfügt, um einen Verteidiger beizuziehen, Anspruch auf einen unentgeltlichen Rechtsbeistand, wenn dies zur Wahrung seiner Rechte notwendig ist und ihr Rechtsbegehren nicht aussichtslos erscheint. Nach der Rechtsprechung des Bundesgerichts gilt diese verfassungsrechtliche Minimalgarantie nicht nur im Straf- und Zivilprozess sowie im Verwaltungsbeschwerde- und Verwaltungsgerichtsverfahren, sondern auch im nichtstreitigen Verwaltungsverfahren. Das Bundesgericht hat einen Anspruch auf unentgeltliche Verbeiständung namentlich im Verfahren um bedingte oder definitive Entlassung aus dem Vollzug einer Massnahme gemäss Art. 43 aStGB bejaht (<ref-ruling> E. 2.3 mit Hinweis).
2.2.3 Die Vorinstanz heisst den Antrag des Beschwerdeführers auf unentgeltliche Rechtspflege (bzw. Prozessführung) sowohl im Verfahren vor ihr als auch in demjenigen vor dem JSD im angefochtenen Entscheid gut. Daraus folgt, dass sie die Rechtsmittel des mittellosen Beschwerdeführers im kantonalen Verfahren nicht als von vorneherein aussichtslos einstuft. Dem Antrag auf unentgeltliche Rechtsverbeiständung gibt sie jedoch nicht statt, dies mit der Begründung, ein Anwalt wäre dem Beschwerdeführer im konkreten Verfahrensstadium nicht mehr von Nutzen gewesen bzw. anwaltliche Hilfe käme zu spät. Diese Argumentation ist unhaltbar angesichts dessen, dass der Beschwerdeführer bereits anlässlich der mündlichen Anhörung vor der Vollzugsbehörde am 14. Januar 2009 einen Antrag auf Beigabe eines unentgeltlichen Rechtsbeistands stellte und er diesen Antrag in jedem Verfahrensabschnitt rechtzeitig mit Erhebung des Rekurses erneuerte. Dass das Rechtsmittel des Beschwerdeführers als Sprungrekurs an die Vorinstanz überwiesen wurde, darf ihm nicht zum Nachteil gereichen. Mit der Frage der Notwendigkeit einer Verbeiständung befasst sich die Vorinstanz in der Folge nicht. Zu berücksichtigen ist insofern, dass das Verfahren betreffend bedingte Entlassung für den seit 1988 bzw. 1995 im Massnahmenvollzug befindlichen Beschwerdeführer von erheblicher Bedeutung ist (vgl. <ref-ruling> E. 2.4.4). Die Entscheidgrundlagen (psychiatrisches Gutachten, Fachkommissionsbericht, Therapie- und Anstaltsleitungsbericht) sind komplex, deren Würdigung anspruchsvoll und für einen juristischen Laien wie den Beschwerdeführer schwierig. Dies gilt umso mehr, als es darin um seinen eigenen Geistes- und Gesundheitszustand im Zusammenhang mit der Frage nach der Rückfallgefährlichkeit bzw. einer möglichen Bewährung in Freiheit geht (vgl. a.a.O., E. 2.5.2, S. 235). Dass das psychiatrische Gutachten vom 31. Oktober 2007 noch nie von einem Anwalt auf die im Verfahren betreffend bedingte Entlassung sich stellenden Fragen hin evaluiert bzw. überprüft wurde, fällt zusätzlich ins Gewicht. Weiter ist nicht zu übersehen, dass sich das kantonale Verfahren nicht einfach gestaltete (mangelhafte Akteneinsicht anlässlich der Anhörung, Sprungrekurs, Replik). Dass der Beschwerdeführer auf sich alleine gestellt nicht in der Lage war, seine Interessen selber wirksam wahrzunehmen, zeigt sich denn nicht zuletzt daran, dass die Vorinstanz die Beschwerde - aus formellen Gründen - materiell kaum behandelt bzw. sie eine fehlende Auseinandersetzung des Beschwerdeführers mit den Ausführungen in den Entscheidgrundlagen feststellt (angefochtener Entscheid, S. 3 f., S. 8). Aus all dem folgt, dass dem Beschwerdeführer im kantonalen Verfahren ein unentgeltlicher Rechtsvertreter zur Wahrung seiner Rechte hätte beigegeben werden müssen. Dies kann nicht mit der Begründung beiseite geschoben werden, es sei nicht Sache des Gerichts, dem Beschwerdeführer einen Anwalt zu suchen. Der angefochtene Entscheid verletzt den Anspruch auf unentgeltliche Rechtsverbeiständung.
2.3 Nachdem der angefochtene Entscheid aus formellen Gründen aufzuheben ist und im Kanton über die Angelegenheit neu zu entscheiden ist, erübrigt es sich, auf die materiellen Vorbringen des Beschwerdeführers einzugehen.
3. Die Beschwerde ist damit gutzuheissen, der angefochtene Entscheid aufzuheben und die Sache zur neuen Beurteilung an die Vorinstanz zurückzuweisen. Da der Beschwerdeführer obsiegt, sind ihm für das bundesgerichtliche Verfahren keine Kosten aufzuerlegen. Er ist vor Bundesgericht nicht anwaltlich vertreten. Besondere persönliche Aufwendungen, die er gehabt haben könnte, macht er nicht geltend. Es ist ihm deshalb keine Entschädigung zuzusprechen (<ref-ruling> E. 4; <ref-ruling> E. 5). Bei diesem Ausgang des Verfahrens ist das Gesuch um unentgeltliche Rechtspflege und Verbeiständung gegenstandslos geworden.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen, der Entscheid des Appellationsgerichts des Kantons Basel-Stadt vom 16. September 2009 aufgehoben und die Sache an die Vorinstanz zur neuen Beurteilung zurückgewiesen.
2. Es werden keine Kosten erhoben.
3. Dieses Urteil wird den Parteien und dem Appellationsgericht des Kantons Basel-Stadt als Verwaltungsgericht schriftlich mitgeteilt.
Lausanne, 22. März 2010
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Favre Arquint Hill