Sachverhalt:
A. Der 1954 geborene X._ befindet sich im Massnahmenvollzug. Er wurde gestützt auf die Urteile des Obergerichts und des Geschworenengerichts des Kantons Zürich vom 9. März 1978 und vom 6. Mai 1985 im Sinne von Art. 43 Ziff. 1 Abs. 2 aStGB verwahrt. Seit Mai 1997 wurde die Massnahme in der Strafanstalt S._ vollzogen. Mit Verfügung vom 6. Oktober 2003 wurden X._ unbegleitete zwölfstündige Beziehungsurlaube bewilligt. Die Versetzung vom geschlossenen in den offenen Vollzug im Haus "H._" wurde ihm mit Verfügung vom 19. Januar 2006 gewährt. Am 17. Mai 2006 wurde X._ die Bewilligung für zwei tägliche Spaziergänge von etwa 30 Minuten mit den Hunden des Hauses "H._" erteilt.
Im Zusammenhang mit dem Urlaubsmissbrauch eines verwahrten Drittinsassen ordnete der Vorsteher der Justizdirektion des Kantons Zürich am 24./25. August 2006 die sofortige Aussetzung und Neubeurteilung der Vollzugslockerungen mit unbegeleiteten Bewegungsmöglichkeiten für alle Verwahrten des Kantons Zürich an. Die X._ gewährten unbegleiteten Urlaube inklusive Spaziergänge mit den Hunden wurden in der Folge am 4. September 2006 sistiert. Eine Rückversetzung in den geschlossenen Verwahrungsvollzug erfolgte nicht. Am 28. Dezember 2006 wurde ihm eröffnet, dass eine Rückversetzung ins geschlossene Regime zwingend sei, wenn er sich nicht innert nützlicher Frist bereit erkläre, sich in eine Therapie einbinden zu lassen. Bis dahin würde die Sistierung betreffend die zwölfstündigen unbegleiteten Urlaube und das Ausführen der Hunde aufrechterhalten. Am 10. Januar 2007 bestand das Amt für Justizvollzug auf einer Einbindung des Beschwerdeführers in eine deliktorientierte Therapie des psychiatrisch-psychologischen Diensts (PPD) des Justizvollzugs des Kantons Zürich.
Mit Verfügung vom 19. März 2007 widerrief das Amt für Justizvollzug die X._ gewährten Ausgangs- und Urlaubsbewilligungen und versetzte ihn per sofort zurück in den geschlossenen Vollzug der Strafanstalt S._. Aufgrund des hohen bis sehr hohen strukturellen Rückfallrisikos sei von einer erhöhten Gefahr für Dritte auszugehen. Deshalb seien zum Schutz der Öffentlichkeit ein weiterer Verbleib X._s im offenen Vollzug und die Gewährung von unbegleiteten Urlauben bzw. Spaziergängen ohne Einbindung in ein deliktorientiertes therapeutisches Setting nicht mehr zu verantworten.
B. Den an die Justizdirektion gerichteten Rekurs X._s leitete diese mit der Begründung, sie sei vorbefasst, an den Regierungsrat des Kantons Zürich zur Behandlung weiter. Mit Beschluss vom 31. Oktober 2007 erklärte sich dieser für zuständig und wies das Rechtsmittel ab, soweit es nicht gegenstandslos geworden war.
C. Dagegen reichte X._ sowohl beim Verwaltungsgericht des Kantons Zürich als auch beim Bundesgericht Beschwerde ein. Das bundesgerichtliche Verfahren blieb bis zum Entscheid des Verwaltungsgerichts sistiert. Dieses trat mit Beschluss vom 24. Dezember 2007 auf die Beschwerde wegen fehlender Zuständigkeit nicht ein. Der verwaltungsgerichtliche Beschluss ist in Rechtskraft erwachsen. X._ beantragt vor Bundesgericht, es seien die Dispositivziffern I und II des Rekursentscheids des Regierungsrats des Kantons Zürich vom 31. Oktober 2007 sowie die Verfügung des Amtes für Justizvollzug vom 19. März 2007 betreffend Verwahrungsvollzug (Rückversetzung in den geschlossenen Vollzug, Widerruf der Ausgangs- und Urlaubsbewilligung) aufzuheben und er sei - unter Wiedergewährung der ihm bisher bewilligten Urlaube und Spaziergänge mit den Hunden - per sofort in den offenen Verwahrungsvollzug zurückzuversetzen. Eventualiter sei die Sache an die Vorinstanz zur Neubeurteilung zurückzuweisen.
D. Das Amt für Justizvollzug und der Regierungsrat des Kantons Zürich beantragen in ihren Eingaben vom 18. bzw. 20. März 2008 die Abweisung der Beschwerde.

Erwägungen:
1. Da der Kanton Zürich seiner Verpflichtung von <ref-law>, in Strafsachen als letzte kantonale Instanzen Gerichte einzusetzen, noch nicht nachgekommen ist, und dies auch noch nicht tun musste (<ref-law>), ist der angefochtene Entscheid des Regierungsrats, gegen den das geltende kantonale Verfahrensrecht kein Rechtsmittel zulässt, kantonal letztinstanzlich im Sinne von <ref-law>. Dies trifft auf die Verfügung des Amts für Justizvollzug nicht zu. Soweit der Beschwerdeführer die Aufhebung auch dieser Verfügung verlangt, kann auf die Beschwerde deshalb nicht eingetreten werden. Der Entscheid über die Rückversetzung in den geschlossenen Verwahrungsvollzug inklusive Widerruf der Vollzugslockerungen mit freier Bewegungsmöglichkeit (Rücknahme der Urlaubs- und Ausgangsbewilligung) betrifft eine Strafsache gemäss <ref-law>. Die Beschwerde in Strafsachen ist damit zulässig. Der Beschwerdeführer ist auch befugt, sie zu erheben, da er durch den genannten Entscheid in seinen rechtlich geschützten Interessen betroffen ist (<ref-law>). Er rügt einen unzulässigen Eingriff in seine verfassungsmässigen Rechte auf persönliche Freiheit (<ref-law>, Art. 5 Abs. 1 lit. a und Abs. 3 EMRK, <ref-law>) und auf Achtung seines Privat- und Familienlebens (<ref-law>, Art. 8 EMRK), einen Verstoss gegen das Willkürverbot (<ref-law>) sowie eine Verletzung des Grundsatzes des "fair trial" (Art. 6 EMRK) und des Gehörsanspruchs (<ref-law>) sowie eine unrichtige Anwendung von <ref-law> und Art. 42 aStGB. Diese Rügen sind zulässig im Sinne von <ref-law>. Auf die Beschwerde kann insoweit eingetreten werden.
2. Art. 6 Ziff. 1 EMRK räumt Personen bei Streitigkeiten über zivilrechtliche Ansprüche und Verpflichtungen sowie in Verfahren über eine gegen sie erhobene strafrechtliche Anklage das Recht auf Beurteilung durch ein Gericht in einem fairen Verfahren ein. Die Anwendung von Art. 6 EMRK setzt unter anderem voraus, dass es um die Stichhaltigkeit einer strafrechtlichen Anklage geht. Nach Auffassung der Konventionsorgane heisst dies, dass das Verfahren darauf gerichtet sein muss, Schuld oder Nichtschuld der angeklagten Person festzustellen und/oder die Strafe festzusetzen. Verfahren, welche in einem weiteren Sinn zwar auch strafrechtlicher Natur sind, diese Merkmale aber nicht erfüllen, unterstehen dem Geltungsbereich von Art. 6 EMRK nicht (Theo Vogler, Internationaler Kommentar zur Europäischen Menschenrechtskonvention, Rz. 218 zu Art. 6 EMRK; Mark E. Villiger, Handbuch der Europäischen Menschenrechtskonvention, 2. Aufl., Zürich 1999, Rz. 401). Der Beschwerdeführer beruft sich zu Unrecht auf diese Verfahrensgarantie, zumal es im zu beurteilenden Fall nicht (mehr) um eine gegen ihn erhobene Anklage im Sinne von Art. 6 Ziff. 1 EMRK geht, sondern um reine Strafvollzugsstreitigkeiten (Versetzung vom offenen in den geschlossenen Vollzug mit Widerruf der Urlaubs- und Ausgangsbewilligung). Die angerufene EMRK-Bestimmung findet hier folglich keine Anwendung.
Auch die Berufung auf <ref-law> und Art. 5 EMRK erfolgt vorliegend zu Unrecht. Die in den genannten Artikeln gewährleistete persönliche Freiheit schützt als Menschenrecht vor willkürlicher Freiheitsentziehung und garantiert eine richterliche Kontrolle des Freiheitsentzugs. Personen, denen die Freiheit bereits entzogen ist, können sich allerdings grundsätzlich nicht auf diese Bestimmungen berufen, wenn der ihnen verbliebene Raum durch eine behördliche Massnahme weiter eingeschränkt wird (vgl. Christoph Grabenwarter, Europäische Menschenrechtskonvention, 2. Aufl., Wien 2005, S. 149 Rz. 1; Walter Gollwitzer, Menschenrechte im Strafverfahren, MRK und IPBPR, Berlin 2005, Rz. 25 zu MRK Art. 5; siehe auch Hans Vest, St. Galler Kommentar, Rz. 3 ff. zu <ref-law>). Der Beschwerdeführer wurde gestützt auf die rechtskräftigen Urteile des Obergerichts und des Geschworenengerichts des Kantons Zürich aus den Jahren 1978 und 1985 verwahrt. Die vorliegend ihm gegenüber verfügten Freiheitsbeschränkungen, d.h. die Rückversetzung vom offenen in den geschlossenen Vollzug mit Widerruf der Urlaubs- und Ausgangsbewilligung, betreffen den blossen Vollzug der Massnahme und fallen deshalb nicht in den Schutzbereich von <ref-law> und Art. 5 EMRK.
Die Beschwerde ist insoweit als unbegründet abzuweisen, soweit darauf überhaupt eingetreten werden kann.
3. Zusammengefasst hat der Regierungsrat im angefochtenen Entscheid erwogen, dass es den Lockerungsentscheiden vom 6. Oktober 2003, 19. Januar und 17. Mai 2006 an einer genügend tragfähigen Grundlage fehle, weil sich an der Gefährlichkeit des Beschwerdeführers trotz jahrelanger Verwahrung nichts geändert habe. Der vorliegend angefochtene Widerruf dieser Entscheide sei deshalb nicht rechtsverletzend, sondern im vorrangigen Interesse der Öffentlichkeit, vor der Gemeingefährlichkeit des Beschwerdeführers geschützt zu werden, notwendig gewesen. Der angefochtene Widerruf sei auch deshalb nicht ungerechtfertigt, weil der Beschwerdeführer seine gesetzliche Pflicht verletzt habe, an der Erreichung des Vollzugsziels mitzuwirken, indem er sich weigere, eine deliktorientierte Psychotherapie aufzunehmen (angefochtener Entscheid, S. 19).
4. Der Beschwerdeführer rügt das rechtliche Gehör gemäss <ref-law> als verletzt. Was er in diesem Zusammenhang vorbringt, geht an der Sache vorbei. Der Regierungsrat hat sich im angefochtenen Entscheid entgegen der Meinung des Beschwerdeführers mit seinen Vorbringen befasst, eine "Therapie" in der Strafanstalt absolviert zu haben und therapiewillig zu sein. Im Übrigen steht fest, dass der Beschwerdeführer nicht willens ist, sich auf eine deliktorientierte Therapie PPD einzulassen. Dass und inwiefern der vom Regierungsrat gezogene Schluss, der Beschwerdeführer sei nicht bereit, eine (solche) Therapie in Angriff zu nehmen, schlechterdings nicht vertretbar sein sollte, ist vor diesem Hintergrund nicht einzusehen. Die insoweit erhobene Willkürrüge des Beschwerdeführers ist unbegründet (Beschwerde, S. 11/12; angefochtener Entscheid, S. 17/18).
5. Der Beschwerdeführer wirft dem Regierungsrat sinngemäss eine willkürliche Beweiswürdigung hinsichtlich der Einschätzung seiner Gemeingefährlichkeit vor. Er macht insbesondere geltend, sich seit Jahren im Vollzug in hervorragender Weise bewährt zu haben. Dafür, dass von ihm eine Gefahr ausgehen könnte, gebe es keinerlei konkrete Hinweise (Beschwerde, S. 12/13).
Der Regierungsrat stützt sich bei seiner Gefährlichkeitsbeurteilung in erster Linie auf die zahlreichen, bei den Akten liegenden psychiatrischen Gutachten vom 27. April 1983, vom 12. April 1985, vom 25. Juni 1991, vom 27. April 1994 sowie vom 18. Mai 1999. Das Fehlen weiterer aussagekräftiger Berichte neueren Datums mit Lang- und Kurzzeitprognosen sei auf die abwehrende Haltung des Beschwerdeführers gegenüber den Mitarbeiterinnen und Mitarbeitern des PPD Zürich zurückzuführen. Den PPD-Berichten aus den Jahren 1999 bis 2006 liessen sich deshalb keine konkreten Ausführungen zum Rückfallrisiko des Beschwerdeführers entnehmen; der genannte Dienst habe sich dazu ausser Stande gesehen, weil der Beschwerdeführer keine eigentliche Therapie absolviere. Es müsse daher aufgrund der erwähnten Gutachten davon ausgegangen werden, dass keine entscheidende Veränderung der Persönlichkeitsmerkmale des Beschwerdeführers stattgefunden habe, er die Öffentlichkeit also nach wie vor in schwerwiegender Weise gefährde. Auch aus den FOTRES-Bewertungen vom 1./8. November 2006, in deren Rahmen die Gemeingefährlichkeit des Beschwerdeführers erneut beurteilt worden sei, liesse sich nichts Gegenteiliges ableiten. Diese hätten betreffend den Beschwerdeführer vielmehr ein deutliches bis sehr hohes strukturelles Rückfallrisiko ergeben und hohe Werte bezüglich "Aggressionsfokus", "Waffeneinsatz", "Gewaltbereitschaft" und "Progredienz" gezeigt. An dieser Gefährlichkeitseinschätzung vermöge das tadellose Verhalten des Beschwerdeführers im Vollzug nichts zu ändern. Die Tatsache, dass er sich im Rahmen der Vollzugslockerungen nichts zu Schulden habe kommen lassen, sowie die durchwegs positiven Berichte seiner sozialen Umgebung (Werkmeister, Pfarrer) seien zwar nicht unwichtige Indizien dafür, dass seit der Rückversetzung in den geschlossenen Verwahrungsvollzug im Jahre 1995 eine positive Entwicklung der Persönlichkeit des Beschwerdeführers eingesetzt habe. Doch sei - ausgehend davon, dass sich an der Gefährlichkeit des Beschwerdeführers trotz jahrelanger Verwahrung grundsätzlich nichts geändert habe - die Gewährung von Vollzugslockerungen ohne Aufnahme einer delikt-orientierten Therapie zur Minimierung des Sicherheitsrisikos für die Öffentlichkeit nicht mehr zu verantworten (angefochtener Entscheid, S. 10 ff.).
Die Feststellung des Regierungsrats, dass der Beschwerdeführer nach wie vor gemeingefährlich ist, beruht auf einer eingehenden Beweiswürdigung, die auch die zu Gunsten des Beschwerdeführers sprechenden Umstände mit berücksichtigt. Was in der Beschwerde dagegen vorgebracht wird, erschöpft sich in einer appellatorischen Kritik am angefochtenen Entscheid, die zur Begründung der Willkürrüge nicht genügt. Soweit sich der Beschwerdeführer mit der Beweiswürdigung im angefochtenen Entscheid überhaupt befasst, setzt er dieser lediglich seine abweichende Sicht der Dinge gegenüber. Er legt nicht substantiiert dar, inwiefern die Beweiswürdigung, in deren Rahmen auf seine nach wie vor bestehende Gefährlichkeit geschlossen wird, schlechterdings unhaltbar sein sollte. Die Beschwerde genügt damit den Begründungsanforderungen gemäss <ref-law> nicht. Inwieweit bei dieser Sachlage, d.h. der willkürfreien Einschätzung des Beschwerdeführers als gemeingefährlich, die von ihm angerufenen verfassungsmässigen Rechte auf persönliche Freiheit sowie auf Achtung seines Privat- und Familienlebens verletzt sein könnten, wird in der Beschwerde nicht dargetan und ist im Übrigen auch nicht ersichtlich, zumal es verfassungsrechtlich als unbedenklich erscheint, einem willkürfrei als gemeingefährlich eingestuften Strafttäter Vollzugserleichterungen zum Schutz der Allgemeinheit vor der von ihm ausgehenden Gefahr zu entziehen bzw. nur mehr unter Bedingungen zu gewähren, die geeignet sind, die Gemeingefährlichkeit zu verringern und die Entwicklung des Betroffenen besser zu beurteilen. Die Beschwerde ist in diesem Punkt demnach als unbegründet abzuweisen, soweit darauf überhaupt einzutreten ist.
6. Der Beschwerdeführer wehrt sich gegen die Verknüpfung von Vollzugslockerungen mit der Durchführung einer deliktorientierten Therapie. Die bisherigen Vollzugslockerungen, in deren Rahmen er sich stets klaglos verhalten habe, seien nie davon abhängig gemacht worden, sich einer solchen Therapie unterziehen zu müssen. Es sei deshalb willkürlich und unfair, die Rückversetzung nunmehr plötzlich damit zu begründen, der Beschwerdeführer habe sich einer entsprechenden (angeblichen) Verpflichtung zur Mitwirkung entzogen (Beschwerde, S. 10).
Nach Auffassung des Regierungsrats widersprechen die strittigen Vollzugslockerungen (auch) der vom Gesetz vorgegebenen Vollzugsplanung. Diese müsse die Verringerung des Rückfallsrisikos und die Verbesserung der langfristigen Legalprognose anstreben (Art. 20 StJVG/ZH). Dieses Vollzugsziel könne beim Beschwerdeführer gemäss gutachtlicher Einschätzung - wenn überhaupt - nur erreicht werden, wenn er eine thematisch verbundene Psychotherapie mit Behandlungsvertrag aufnehme. Weil den Beschwerdeführer im Hinblick auf die Erreichung des Vollzugsziels eine gesetzliche Mitwirkungspflicht treffe und dieses Ziel nur erreicht werden könne, wenn er eine entsprechende Psychotherapie mit Behandlungsvertrag aufnehme, habe er sich einer solchen zu stellen. Andernfalls könnten ihm keine Urlaube oder Ausgänge mit unbegleiteten Bewegungsmöglichkeiten mehr gewährt werden und sei auch eine Versetzung in den offenen Verwahrungsvollzug ausgeschlossen (angefochtener Entscheid, S. 16).
Wie bereits ausgeführt wurde, ist der Beschwerdeführer nach der willkürfreien Einschätzung des Regierungsrats nach wie vor als gemeingefährlich anzusehen. Er möchte weiterhin von den ihm bislang bewilligten Vollzugserleichterungen profitieren, ist aber nicht willens, eine regelmässige, über die Erörterung von Alltagsanlässen hinausgehende und thematisch verbundene Psychotherapie mit Behandlungsvertrag beim PPD aufzunehmen. Dadurch verletzt er nach richtiger Auffassung des Regierungsrats grundsätzlich seine gesetzliche Mitwirkungspflicht im Hinblick auf die Erreichung des Vollzugsziels zur Vermeidung von Rückfällen, zumal die verlangte Einbindung des Beschwerdeführers in eine deliktorientierte Therapie die Verringerung seiner Gefährlichkeit und damit die Minimierung des Sicherheitsrisikos für die Allgemeinheit zum Zweck hat. Der Straftäter, der sich dieser gesetzlichen Mitwirkungspflicht ohne triftige Gründe entzieht, hat die Konsequenzen daraus zu tragen. Diese können in der Verweigerung von Vollzugslockerungen bestehen. Das vom Regierungsrat geschützte Vorgehen des Amts für Justizvollzug ist folglich nicht zu beanstanden. Daran ändert nichts, dass dem Beschwerdeführer trotz Gemeingefährlichkeit in der Vergangenheit - ohne entsprechende Therapie - Vollzugserleichterungen gewährt wurden und er sich in deren Rahmen nie etwas zu Schulden hat kommen lassen. Denn es ist das Recht und die Pflicht der zuständigen Behörden, das Vollzugsregime - egal aus welchem Anlass - im Rahmen der gesetzlichen Möglichkeiten periodisch zu überprüfen und zum Schutze der Öffentlichkeit eventuell gewährte Vollzugserleichterungen gegenüber willkürfrei als gemeingefährlich eingestuften Straftätern zurückzunehmen bzw. von Bedingungen abhängig zu machen, die geeignet sind, die festgestellte Gefährlichkeit des Betroffenen zu verringern und dessen Entwicklung besser zu beurteilen. Aus diesen Gründen erscheint es nicht als willkürlich und auch nicht als übermässiger Eingriff in die vom Beschwerdeführer angerufenen verfassungsmässigen Rechte auf persönliche Freiheit sowie auf Schutz seines Privat- und Familienlebens, die Gewährung von Vollzugserleichterungen, d.h. die Rückversetzung in den offenen Vollzug sowie Urlaube und Ausgänge mit unbegeleiteter Bewegungsmöglichkeit, an die Durchführung einer deliktorientierten Therapie zu knüpfen.
Soweit der Beschwerdeführer in diesem Zusammenhang auch eine unrichtige Anwendung von Art. 42 aStGB und <ref-law> geltend macht (Beschwerde, S. 9/11), zielt seine Rüge an der Sache vorbei. Denn Gegenstand des vorliegenden Verfahrens bildet einzig der Massnahmenvollzug, nicht aber das Verwahrungsrecht als solches.
7. Zusammenfassend erweist sich die Beschwerde in Strafsachen als unbegründet. Sie ist daher abzuweisen, soweit darauf eingetreten werden kann. Der Beschwerdeführer stellt ein Gesuch um unentgeltliche Rechtspflege (unentgeltliche Prozessführung und Rechtsverbeiständung). Da die gesetzlichen Voraussetzungen erfüllt sind, kann dem Begehren entsprochen werden (Art. 64 Abs. 1 - 2 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird gutgeheissen.
3. Es werden keine Kosten erhoben.
4. Rechtsanwältin Caterina Nägeli wird als unentgeltliche Rechtsbeiständin des Beschwerdeführers bestellt, und es wird ihr für das bundesgerichtliche Verfahren aus der Bundesgerichtskasse eine Entschädigung von Fr. 2'000.-- ausgerichtet.
5. Dieses Urteil wird den Parteien, dem Regierungsrat des Kantons Zürich und dem Verwaltungsgericht des Kantons Zürich schriftlich mitgeteilt.
Lausanne, 9. April 2008
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Schneider Arquint Hill