Sachverhalt: A. X._ (geb. am xx.xx.1937) wurde mit Urteilen des Bezirksgerichts Zofingen vom 26. Oktober 1989 und des Kreisgerichts Churwalden vom 11. Dezember 1990 wegen mehrfacher sexueller Handlungen mit Kindern (bzw. dannzumal wegen wiederholter und fortgesetzter Unzucht mit Kindern) insgesamt zu einer Freiheitsstrafe von 19 Monaten verurteilt. Sowohl die zunächst angeordnete ambulante Behandlung als auch die in der Folge verhängte stationäre therapeutische Massnahme blieben ohne Erfolg. Auf Ersuchen der Schutzaufsicht Graubünden vom 10. September 1992 entschied das Kantonsgericht von Graubünden am 12. November 1992, X._ gestützt auf Art. 43 Ziff. 1 Abs. 2 aStGB zu verwahren. Seine Nichtigkeitsbeschwerde wies das Bundesgericht am 24. März 1993 ab, soweit es darauf eintrat (Urteil 6S.105/1993). Am 20. Juli 1993 sprach das Kreisgericht Lugnez X._ erneut der mehrfachen sexuellen Handlungen mit Kindern und der Pornographie schuldig und bestrafte ihn mit drei Monaten Freiheitsstrafe. Der Vollzug der Strafe wurde zugunsten der Verwahrung aufgeschoben. Auf Berufung von X._ hin sprach ihn das Kantonsgericht von Graubünden am 22. September 1993 vom Vorwurf der Pornographie frei, reduzierte die Strafe auf zwei Monate und bestätigte die angeordnete Verwahrung. Mit Entscheid vom 5. Dezember 2007 beschloss das Kantonsgericht von Graubünden, die altrechtlich angeordnete Verwahrung mangels Therapierbarkeit von X._ in Anwendung von Art. 64 StGB und Ziff. 2 Abs. 2 SchlBestStGB nach neuem Recht weiterzuführen. B. Im Rahmen der jährlichen Massnahmeüberprüfung lehnte es das Amt für Justizvollzug Graubünden jeweils ab, X._ bedingt aus der Verwahrung zu entlassen, letztmals am 6. Oktober 2010. Die von X._ gegen diesen Entscheid erhobene Beschwerde wies das Departement für Justiz, Sicherheit und Gesundheit des Kantons Graubünden am 17. Januar 2011 ab. Das Kantonsgericht von Graubünden hiess die dagegen ergriffene Beschwerde von X._ am 6. April 2011 insofern gut, als es die angefochtene Verfügung aufhob und die Sache insbesondere zur Einholung eines psychiatrischen Zusatzgutachtens zwecks aktueller legalprognostischer Beurteilung und zur Neuentscheidung an das Amt für Justizvollzug zurückwies. Nach Eingang des psychiatrischen Zusatzgutachtens vom 31. Oktober 2011 und eines Vollzugsberichts der Strafanstalt Z._ sowie nach Gewährung des rechtlichen Gehörs lehnte es das Amt für Justizvollzug Graubünden am 19. Januar 2012 erneut ab, X._ bedingt aus der Verwahrung zu entlassen. Die dagegen geführte Beschwerde wies das Departement für Justiz, Sicherheit und Gesundheit des Kantons Graubünden am 2. Mai 2012 ab. Das Kantonsgericht von Graubünden hiess die Berufung von X._ am 19./21. Dezember 2012 insofern teilweise gut, als es diesem die amtliche Verteidigung rückwirkend gewährte und über die Kostenregelung neu befand. Im Übrigen wies es die Berufung in Bestätigung der Verfügung des Departements für Justiz, Sicherheit und Gesundheit des Kantons Graubünden vom 2. Mai 2012 ab. C. Mit Beschwerde in Strafsachen beantragt X._, der Beschluss des Kantonsgerichts von Graubünden sei aufzuheben, und er sei aus der Verwahrung zu entlassen. Ausserdem sei die Verletzung des Beschleunigungsgebots durch die Vorinstanzen festzustellen und die Sache zur Festsetzung einer Entschädigung und Genugtuung für den unrechtmässigen Freiheitsentzug seit 1. Januar 2007, eventuell seit 12. November 1992, an die Vorinstanz zurückweisen. Eventuell sei der Kanton Graubünden zu verpflichten, ihm für die unrechtmässige Haft sowie für die Verletzung des Beschleunigungsgebots eine angemessene Entschädigung/Genugtuung in der Höhe von mindestens Fr. 500.-- pro Tag zu bezahlen. X._ ersucht um unentgeltliche Rechtspflege und Verbeiständung. D. Das Kantonsgericht von Graubünden verzichtet auf die Einreichung einer Stellungnahme zur Beschwerde. Das Amt für Justizvollzug beantragt, die Beschwerde abzuweisen.