Faits:
A. X._ a été arrêté et placé en détention préventive, le 29 décembre 2009, après avoir frappé, sans aucune raison, à coups de poing et de pied une personne et avoir menacé verbalement et avec un couteau une autre. Lors de la perquisition de son domicile, la police a découvert et séquestré un couteau, 18 grammes de marijuana, une seringue et une machette/hachoir.
Durant l'enquête, une expertise psychiatrique a été ordonnée. Dans leur rapport du 14 avril 2010, les experts ont posé le diagnostic de schizophrénie paranoïde. De leur point de vue, au moment des faits, X._ n'était pas en mesure d'apprécier le caractère illicite de ses actes ni de se déterminer d'après cette appréciation en raison de ses idées délirantes de persécution. Une mesure institutionnelle au sens de l'<ref-law>, réalisée en milieu fermé et accompagnée d'un traitement psychiatrique et neuroleptique, était indiquée.
Par jugement du 17 août 2010, le Juge des districts de Martigny et St-Maurice a condamné X._ pour contravention à la loi fédérale sur les stupéfiants (<ref-law>) et violation de l'art. 33 al. 1 let. a de la loi fédérale sur les armes, les accessoires d'armes et les munitions à une peine pécuniaire de 15 jours-amende et à une amende de 500 francs. Il l'a exempté de toute peine pour les faits en relation avec la violation des art. 123 al. 1 et 180 al. 1 CP (lésions corporelles simples et menaces) et ordonné un traitement institutionnel dans un établissement psychiatrique ou pénitentiaire fermé ou dans la section fermée d'un établissement pénitentiaire ouvert (<ref-law>).
B. B.a Dès le 20 octobre 2010, X._ a requis sa libération conditionnelle auprès de la direction de la Prison des Iles et du Juge du Tribunal des districts de Martigny et Saint-Maurice.
Le 25 mars 2011, son conseil a déposé auprès du Tribunal de l'application des peines et mesures du canton du Valais une requête tendant à la levée de la mesure ordonnée, subsidiairement à son remplacement par un traitement ambulatoire au sens de l'<ref-law>, plus subsidiairement par un traitement institutionnel en milieu ouvert. A titre de mesures provisoires, il a demandé son transfert soit à l'hôpital psychiatrique de Malévoz, soit à la colonie pénitentiaire de Crêtelongue. En outre, il a sollicité l'octroi de l'assistance judiciaire et la mise en oeuvre de diverses mesures d'instruction.
B.b Par ordonnance du 24 mai 2012, le Tribunal de l'application des peines et mesures du canton du Valais a refusé à X._ la libération conditionnelle, mis les frais à la charge de l'Etat du Valais et dit que ce dernier verserait au conseil de X._ une indemnité de 2'850 fr. à titre de dépens pour l'assistance judiciaire.
B.c Par ordonnance du 9 juillet 2012, la Chambre pénale du Tribunal cantonal valaisan a rejeté, dans la mesure de sa recevabilité, le recours formé par X._, mis les frais de la procédure à la charge de l'Etat du Valais, au titre de l'assistance judiciaire gratuite, et dit que ce dernier verserait au conseil de X._ une indemnité de 1'000 fr. au même titre.
B.d X._ forme un recours en matière pénale (réf. 6B.517/2012). Il conclut à la réforme de l'ordonnance du 9 juillet 2012 et requiert que soit constaté que le retard mis par l'autorité de première instance à juger sa cause est contraire à la Constitution fédérale et à la CEDH et qu'une indemnité de 50'000 fr., modification de justice réservée, avec intérêt dès le 25 mars 2011, lui est allouée. Il sollicite pour le surplus sa libération conditionnelle, se soumettant à toutes les conditions qui lui seront fixées, notamment "placement en milieu ouvert ou traitement ambulatoire". Subsidiairement, il requiert l'annulation de l'ordonnance et le renvoi de la cause pour complément d'instruction comme demandé en procédure de première instance. Il réclame enfin une indemnité pour ses dépens, dont au moins 12'000 fr. pour la procédure de première instance, et l'assistance judiciaire pour toutes les procédures. A titre subsidiaire, il requiert le renvoi de la cause à l'autorité précédente pour fixation d'une indemnité. Il sollicite enfin la jonction de la cause avec celle objet de son recours en matière pénale du 20 août 2012 (réf. 6B_471/2012).
B.e Interpellés, la Chambre pénale du Tribunal cantonal valaisan s'est référée à son ordonnance, le Ministère public a renoncé à se déterminer.
C. C.a Par requête du 1er avril 2011, X._ a exigé de la direction des Établissements pénitentiaires du Valais (EPV) qu'elle prenne des décisions formelles sur ses demandes personnelles, les mesures provisionnelles requises dans son courrier du 25 mars 2011 (cf. supra let. Ba), la remise du dossier médical et l'assistance judiciaire.
C.b Par décision du 21 avril 2011, la direction des EPV s'est déclarée incompétente pour statuer sur les courriers de X._ en tant qu'ils concernent la levée de la mesure de traitement institutionnel (I), a constaté que la requête de mesures provisoires, en tant qu'elle vise le transfert vers un autre établissement, ne peut faire l'objet d'une décision administrative (II), a rappelé au service de médecine pénitentiaire qu'il lui incombe d'examiner si et dans quelle mesure le dossier médical de X._ peut être transmis à son conseil (III) et a refusé d'accorder l'assistance judiciaire (IV).
C.c Par arrêt du 18 juin 2012, le Président de la Cour de droit public du Tribunal cantonal valaisan a rejeté, dans la mesure de sa recevabilité, le recours formé par X._ et refusé d'accorder à ce dernier le bénéfice de l'assistance judiciaire. En bref, il a notamment confirmé que la question du transfert vers un autre établissement d'exécution ne pouvait faire l'objet d'une décision. Il a relevé ne pas voir quelle actualité présentait encore, dès le transfert de X._ de la Prison des Iles aux Établissements de la plaine de l'Orbe (EPO), la demande d'une décision sur un placement à Crêtelongue ou à l'hôpital psychiatrique de Malévoz.
C.d X._ forme un recours en matière pénale contre cet arrêt (réf. 6B_471/2012). Il conclut à son annulation et au renvoi de la cause à la direction des EPV, subsidiairement au Tribunal cantonal pour nouvelle décision sur le fond. Il requiert que cette procédure soit jointe à la cause 6B_517/2012. Enfin, il sollicite que l'assistance judiciaire lui soit accordée devant toutes les instances et les frais mis à la charge de l'Etat pour l'ensemble des procédures.
C.e Interpellés sur ce recours, le Président de la Cour de droit public du Tribunal cantonal valaisan et le Ministère public ont renoncé à se déterminer.

Considérant en droit:
1. Le recourant requiert la jonction des causes 6B_471/2012 et 6B_517/2012. Celles-ci ont toutes deux trait à la manière dont la mesure ordonnée est exécutée, respectivement doit l'être. La jonction des causes permettra en outre, à travers l'examen du dossier de la cause 6B_517/2012 de vérifier la réalité des conditions de détention dénoncées par le recourant dans la cause 6B_471/2012, éléments pertinents pour trancher de sa qualité pour recourir (cf. infra consid. 14). Dans la mesure où le recourant, alors qu'il se plaint de la lenteur de la procédure dans la cause 6B_517/2012, requiert lui-même la jonction, rien ne s'oppose à celle-ci.
2. Il est rappelé en préambule que l'acte de recours doit indiquer les motifs, lesquels doivent exposer succinctement en quoi l'acte attaqué viole le droit (art. 42 al. 1 et 2 LTF). Le recourant doit donc discuter les motifs de la décision entreprise et indiquer précisément en quoi il estime que l'autorité précédente a méconnu le droit. Le Tribunal fédéral n'examine en outre les moyens fondés sur la violation de droits fondamentaux, notamment l'interdiction de l'arbitraire, que s'ils ont été invoqués et motivés de manière précise (<ref-law>).
Les moyens du recourant ne seront ainsi examinés que pour autant qu'ils respectent ces exigences. Tel n'est en particulier pas le cas des griefs soulevés sous chiffre VII de son recours 6B_517/2012, le recourant se plaignant de déni de justice sans même préciser quels moyens exactement il aurait soulevés devant l'autorité cantonale qui n'auraient pas été traités par elle.
I. Recours 6B_517/2012 contre l'ordonnance du 9 juillet 2012
3. On comprend des conclusions prises par le recourant qu'il conteste le refus des autorités cantonales de le libérer conditionnellement de l'exécution de son traitement institutionnel en milieu fermé, quitte à prévoir un traitement ambulatoire durant le délai d'épreuve, tout au moins d'ordonner que son traitement institutionnel s'effectue en milieu ouvert.
3.1 3.1.1 La libération conditionnelle d'une mesure est réglée par l'<ref-law>. Elle est accordée dès que l'état de l'auteur justifie qu'on lui donne l'occasion de faire ses preuves en liberté (<ref-law>).
La loi ne définit pas cette notion. Elle n'exige pas la guérison de l'auteur, mais une évolution ayant pour effet d'éliminer ou de réduire dans une mesure suffisante le risque de nouvelles infractions. Il n'est donc pas nécessaire que l'auteur soit mentalement normal. Il suffit qu'il ait appris à vivre avec ses déficits, de manière que l'on puisse poser un pronostic favorable quant à son comportement futur, étant rappelé que s'agissant de la décision sur le pronostic, le principe "in dubio pro reo" est inapplicable (<ref-ruling> consid. 1.2 p. 202 s.).
Ce pronostic doit être posé en tenant compte du principe de la proportionnalité (art. 5 al. 2 Cst. et 56 al. 2 CP) selon lequel l'atteinte aux droits de la personnalité qui résulte pour l'auteur d'une mesure ne doit pas être disproportionnée au regard de la vraisemblance qu'il commette de nouvelles infractions et de leur gravité. Cette disposition postule de la sorte la pesée à effectuer entre l'atteinte aux droits inhérente à la mesure ordonnée et la dangerosité de l'auteur (<ref-ruling> consid. 1.2 p. 202 ).
Présente un caractère de dangerosité le délinquant dont l'état mental est si gravement atteint qu'il est fortement à craindre qu'il commette de nouvelles infractions. Lors de l'examen du risque de récidive, il convient de tenir compte de l'imminence et de la gravité du danger, ainsi que de la nature et de l'importance du bien juridique menacé. Lorsque des biens juridiques importants, tels que la vie ou l'intégrité corporelle, sont mis en péril, il faut se montrer moins exigeant quant à l'imminence et à la gravité du danger que lorsque des biens de moindre valeur, tels que la propriété ou le patrimoine, sont menacés. Le pronostic doit également tenir compte de la durée de la privation de liberté déjà subie par l'auteur (<ref-ruling> consid. 1.2 p. 203).
La libération conditionnelle d'une mesure thérapeutique en milieu fermé au sens de l'<ref-law> n'est pas soumise à des conditions plus strictes que celle d'une autre mesure (MARIANNE HEER, Das neue Massnahmenrecht im Überblick, in Revision des Allgemeinen Teils des Strafgesetzbuches, 2007, p. 123; STEFAN TRECHSEL et al., Schweizerisches Strafgesetzbuch, Praxiskommentar, 2008, n. 2 ad <ref-law>).
3.1.2 Conformément à l'<ref-law>, le traitement institutionnel s'effectue en règle générale dans un établissement psychiatrique approprié ou dans un établissement d'exécution des mesures. L'<ref-law> prévoit toutefois que le traitement doit être exécuté dans un établissement fermé, tant qu'il existe un risque de fuite ou de récidive. Il peut aussi être effectué dans un établissement pénitentiaire au sens de l'<ref-law> - soit dans un établissement fermé ou dans la section fermée d'un établissement ouvert -, si le traitement thérapeutique nécessaire est assuré par du personnel qualifié (art. 59 al. 3 2e phrase CP).
Pour qu'un risque de fuite au sens de cette disposition soit avéré, il faut que l'intéressé ait la ferme et durable intention de s'évader, en ayant recours à la force si nécessaire, et qu'il dispose des facultés intellectuelles, physiques et psychiques nécessaires pour pouvoir établir un plan et le mener à bien. Le fait que l'intéressé puisse tenter de s'enfuir sur un coup de tête et sans aucune préparation préalable ne suffit pas. Il est clair que le risque de fuite devra être lié à la peur que le condamné puisse représenter une menace envers les tiers une fois en liberté (arrêt 6B_372/2012 du 27 septembre 2012 consid. 2.3 et arrêts cités).
Le risque de récidive visé par l'<ref-law> doit quant à lui être concret et hautement probable, c'est-à-dire résulter de l'appréciation d'une série de circonstances. Au regard du principe de la proportionnalité, le placement dans un établissement fermé ne peut être ordonné, respectivement maintenu, que lorsque le comportement ou l'état du condamné représente une grave mise en danger pour la sécurité et l'ordre dans l'établissement. Ce sera par exemple le cas d'un condamné qui profère des menaces bien précises ou qui combat sciemment l'ordre de l'établissement. En revanche, l'<ref-law> ne devrait pas s'appliquer à de simples difficultés de comportement ou à l'insoumission vis-à-vis des employés de l'établissement (cf. arrêt 6B_372/2012 du 27 septembre 2012 consid. 2.3 et arrêts cités).
3.1.3 L'<ref-law> règle la procédure d'examen de la libération et de la levée de la mesure. Il impose à l'autorité compétente, préalablement à sa décision, d'entendre l'auteur et de demander un rapport à la direction de l'établissement chargé de l'exécution de la mesure. Le rapport exigé par cette disposition doit émaner du médecin traitant, dresser un bilan du traitement, comporter les éléments d'appréciation médicaux utiles à l'évaluation de la dangerosité actuelle de l'auteur et se prononcer sur l'évolution probable de ces éléments en cas de poursuite du traitement selon les modalités les plus indiquées (<ref-ruling> consid. 1.1 p. 202).
L'<ref-law> n'exige pas que le juge s'appuie sur le rapport d'un expert chaque fois qu'il statue sur une mesure. Il est toutefois libre de demander un rapport ou une expertise s'il l'estime nécessaire (arrêt 6B_274/2012 du 31 août 2012 consid. 1.1.2).
L'<ref-law> n'exige pas que le juge s'appuie sur le rapport d'un expert chaque fois qu'il statue sur une mesure. Il est toutefois libre de demander un rapport ou une expertise s'il l'estime nécessaire (arrêt 6B_274/2012 du 31 août 2012 consid. 1.1.2).
3.2 3.2.1 L'ordonnance entreprise, datée du 9 juillet 2012, reprend le contenu des rapports demandés, indiquant notamment que celui du service médical des EPO du 22 novembre 2011 constate une amélioration de l'état psychique du recourant, avec quasi-disparition des symptômes négatifs de sa maladie, depuis son affectation à l'atelier de menuiserie-ébénisterie (soit deux mois auparavant; pièce 406; <ref-law>) et que cette évolution pousse les auteurs du rapport à croire qu'un élargissement du cadre carcéral serait bénéfique pour le recourant (ordonnance entreprise, p. 7). Le plan d'exécution de la mesure, validé le 23 avril 2012, retient quant à lui que le recourant est bien stabilisé par son traitement médicamenteux et conscient que la prise régulière de ce traitement et la poursuite de son suivi thérapeutique sont de nature à le mettre à l'abri de la récidive. Il propose par conséquent de mettre en place toute une série d'allègements dès la validation du plan d'exécution de la mesure (ibidem, p. 7-8) et indique que le recourant a atteint une stabilité psychique suffisante pour une ouverture du cadre carcéral actuel vers un placement en foyer psychiatrique (ibidem, p. 16).
Se fondant sur ces documents, l'autorité cantonale a considéré que le maintien du traitement institutionnel en milieu fermé ne violait pas le principe de proportionnalité, arguant notamment que le recourant bénéficie d'allégements et que son état s'améliore (ibidem, p. 16 s.).
3.2.2 L'appréciation de la proportionnalité de la mesure, en l'espèce un traitement institutionnel, doit être examinée en mettant en balance d'une part l'atteinte causée au recourant par cette mesure et d'autre part le risque que ce dernier commette de nouvelles infractions et leur gravité (cf. supra consid. 3.1.1). S'agissant d'un traitement en milieu fermé, cette appréciation doit également tenir compte du risque de fuite, justifiant seul avec celui de récidive au sens de l'<ref-law>, cette mesure très restrictive (cf. supra consid. 3.1.2). Ni la décision entreprise, ni même les rapports auxquels elle se réfère ne contiennent toutefois ces éléments. Il n'est ainsi pas possible de vérifier le bien-fondé de cette décision, soit de déterminer si la mesure ordonnée est toujours proportionnée au risque de fuite et à la dangerosité que présente le recourant et, si tel n'est pas le cas, quelle modification devrait être ordonnée afin de se conformer au principe de proportionnalité.
La cour cantonale s'est à plusieurs reprises référée à des possibilités d'élargissement prévues par le plan d'exécution de la mesure, estimant que la libération conditionnelle n'entre pas en ligne de compte s'il n'y a pas eu au préalable des allégements progressifs, palier par palier dans l'exécution de la mesure (ordonnance entreprise, notamment p. 14). Il est certes prudent, avant d'ordonner la libération, d'observer comment la personne se comporte dans le cadre de la liberté plus grande accordée par le biais d'élargissements. Une telle condition n'est toutefois pas posée par la loi qui exige, non pas que le recourant ait fait ses preuves dans le cadre de l'exécution de la mesure, mais que son état justifie qu'on lui donne l'occasion de faire ses preuves en liberté, dans le cadre précisément de la liberté conditionnelle (<ref-law> et cf. supra consid. 3.1.1). Un refus d'octroi de la liberté conditionnelle ne saurait dès lors en principe reposer sur le seul motif que le recourant n'a pas bénéficié pour l'instant d'allégements. Ce motif tout du moins n'est pas légitime dans le cas d'espèce. En effet, depuis le 22 novembre 2011 au moins, les médecins traitant le recourant ont préconisé un élargissement du cadre carcéral, sans que le recourant n'en bénéficie dans les faits, ce apparemment parce que de tels élargissements devaient être prévus par le plan d'exécution de la mesure. Celui-ci aurait dû être établi au début de l'exécution de la mesure (<ref-law>). Bien que celle-ci ait été ordonnée le 17 août 2010 et commencée le 3 mars 2011, le plan d'exécution de la mesure n'a été validé que le 23 avril 2012. En outre, les premiers élargissements qu'il prévoit ne sont pas accordés au recourant mais devront être demandés (ordonnance entreprise, p. 7), ce qui retardera encore leur mise en place. Force est ainsi de constater que si le recourant n'avait pas bénéficié d'allégements au jour de la décision de première instance, cela résultait de circonstances qui ne lui étaient pas imputables.
Dans ces conditions, l'ordonnance entreprise doit être annulée et la cause renvoyée à l'autorité précédente afin qu'elle établisse, tout au moins en faisant actualiser le rapport visé à l'<ref-law>, les éléments de fait permettant de poser un pronostic relatif aux chances de succès d'une libération conditionnelle, subsidiairement en examinant l'instauration d'une mesure moins contraignante en milieu ouvert (<ref-law>).
3.3 Dans le cadre de cette question, le recourant considère également que le refus des autorités cantonales d'ordonner les mesures d'instruction requises par lui constitue une violation des art. 389 al. 2 et 393 al. 2 let. b CPP. Ces dispositions ne sont pas directement applicables à la procédure de libération conditionnelle (cf. <ref-law>). Pour le surplus, le recourant ne démontre pas conformément aux exigences posées par l'<ref-law> qu'elles auraient constitué du droit cantonal supplétif et auraient été arbitrairement violées. Son moyen est partant irrecevable.
4. Le recourant invoque que l'autorité de première instance aurait tardé à trancher la question de sa libération conditionnelle. Il y voit une violation des <ref-law>, 9, 29 et 31 al. 1 Cst. et 5 par. 4 CEDH. Il conclut à ce que soit constaté que le retard mis par l'autorité de première instance à traiter ce dossier est contraire aux garanties données par la Constitution fédérale et la CEDH et réclame une indemnité.
Telle qu'invoquée, la violation de l'art. 5 par. 4 CEDH se confond avec celle de l'<ref-law>. Le recourant ne formule aucune critique spécifique relative à l'art. 5 par. 4 CEDH qui serait recevable sous l'angle de l'<ref-law>. Le grief tiré de la violation de l'art. 5 par. 4 CEDH est ainsi irrecevable. Il en va de même et pour les mêmes motifs de la violation soulevée des art. 9, 29 et 31 Cst. Il convient dès lors d'entrer en matière uniquement sur la violation invoquée de l'<ref-law>.
5. Aux termes de l'<ref-law>, l'autorité compétente examine, d'office ou sur demande, si l'auteur peut être libéré conditionnellement de l'exécution de la mesure ou si la mesure peut être levée et, si tel est le cas, quand elle peut l'être. Elle prend une décision à ce sujet au moins une fois par an.
5.1 Jusqu'au 1er janvier 2007, l'art. 45 ch. 1 aCP - ancien <ref-law> -, ne prévoyait qu'un examen d'office (et non sur demande) de la question de la libération conditionnelle, au moins une fois par an. Cette disposition a cependant été modifiée afin de se conformer à l'art. 5 par. 4 CEDH qui garantit à toute personne privée de sa liberté par arrestation ou détention le droit d'introduire un recours devant un tribunal, afin qu'il statue à bref délai sur la légalité de sa détention et ordonne sa libération si la détention est illégale (Message du 21 septembre 1998 concernant la modification du code pénal suisse, FF 1999 1787 ss, 1894 ch. 213.435). A l'instar de la procédure instituée en matière d'internement (<ref-law>; arrêts 6B_796/2009 du 25 janvier 2010 consid. 3.4; 6B_33/2009 du 25 février 2009 consid. 3.1 et 3.4), le contrôle, d'office ou sur demande, au moins annuel fixé par l'<ref-law> satisfait à l'exigence d'accès au juge prévue par l'art. 5 par. 4 CEDH (dans ce sens, FF 1999 1894 ch. 213.435). Afin que la possibilité pour l'intéressé de requérir sa libération conditionnelle ne devienne pas lettre morte, l'autorité compétente, saisie d'une telle demande, ne peut se borner à attendre l'échéance du délai d'un an depuis le prononcé de la mesure, respectivement son réexamen, pour statuer sur dite requête. Au contraire, elle doit l'instruire et la trancher le plus rapidement possible (FF 1999 1895 ch. 213.435). La personne soumise à une mesure institutionnelle par un jugement entré en force n'a cependant pas le droit de saisir en tout temps l'autorité d'application des peines et mesures (arrêts 6B_796/2009 du 25 janvier 2010 consid. 3.4; 6B_33/2009 du 25 février 2009 consid. 3.4). La demande, pour être traitée, doit ainsi être formulée après un intervalle raisonnable depuis le prononcé de la mesure, respectivement son réexamen (FF 1999 1894 ch. 213.435). Le caractère raisonnable de l'intervalle est déterminé compte tenu des circonstances d'espèce. Au vu du contrôle au moins une fois par an prescrit par l'<ref-law>, il doit pouvoir être admis avant que douze mois ne se soient écoulés depuis le contrôle précédent.
5.2 L'<ref-law> prévoit un examen d'office ou sur demande. On ne peut dès lors suivre le recourant lorsqu'il distingue plusieurs procédures de libération conditionnelle, à savoir celle instruite d'office, celle instruite à la suite de sa demande du 25 mars 2011 et celle qui aurait dû être ouverte à réception des demandes de libération conditionnelle formulées avant cette date. Il ne saurait en effet y avoir pour un même objet - la libération conditionnelle - visant une même personne et de la compétence d'une seule autorité, plusieurs procédures distinctes en même temps. Tel n'a d'ailleurs pas été le cas en l'espèce. La demande de libération conditionnelle est parvenue à l'autorité de première instance avant l'échéance du délai d'un an depuis le prononcé de la mesure (cf. infra consid. 5.4), de sorte que cette autorité a uniquement instruit une procédure de libération conditionnelle sur demande (décision du 24 mai 2012, p. 1). Elle n'avait en revanche pas à mener parallèlement une procédure d'examen d'office. Les griefs relatifs à une telle procédure sont vains.
5.3 Le délai d'un an prévu par l'<ref-law> est certes contraignant mais n'a pas à être tenu sans réserve, au risque sinon, suivant les circonstances, de rendre une décision ne reposant pas sur tous les éléments nécessaires, respectivement sur des éléments actualisés. Que la question de la libération conditionnelle n'ait pas été examinée un an après le prononcé de la mesure ne viole dès lors pas nécessairement l'<ref-law> si le dépassement peut légitimement s'expliquer par les circonstances d'espèce.
5.4 En l'occurrence, un traitement institutionnel en milieu fermé a été ordonné par jugement du 17 août 2010. Ce jugement n'a pas été attaqué. Entre le 20 octobre 2010 et le 28 janvier 2011, le recourant a requis à cinq reprises sa libération conditionnelle auprès de la direction de la Prison des Iles et du Juge du tribunal des districts de Martigny et Saint-Maurice. Le 3 mars 2011, le recourant, à la suite de son transfert aux EPO, a commencé son traitement. Le 25 mars 2011, son conseil a déposé une requête auprès du tribunal de l'application des peines et mesures tendant à la levée de la mesure, subsidiairement, au remplacement de celle-ci par un traitement ambulatoire au sens de l'<ref-law>, plus subsidiairement par un traitement institutionnel en milieu ouvert. Étaient jointes à cette demande les requêtes préalables de libération conditionnelle formulées par le recourant sans l'assistance d'un avocat. Par décision du 24 mai 2012, le tribunal de l'application des peines et mesures a non seulement refusé de libérer conditionnellement le recourant (décision du 24 mai 2012, p. 19) mais également écarté, sans toutefois l'indiquer dans son dispositif, toutes les autres conclusions du recourant (ibidem, p. 7 à 16). Ce faisant, il a statué sur la question de la libération conditionnelle et de la levée de la mesure 21 mois après le prononcé de celle-ci et 14 mois après qu'une demande en ce sens lui parvienne.
5.5 Il convient d'examiner si, au vu des circonstances d'espèce, le traitement de la demande de libération conditionnelle s'accorde avec les exigences découlant de l'<ref-law>.
5.5.1 La demande du 25 mars 2011 est parvenue au tribunal de l'application des peines et mesures le 29 mars 2011, accompagnée de plus de 140 pages d'annexes. Celui-ci a interpellé le conseil du recourant, par courrier du 30 mars 2011, afin notamment d'obtenir les documents nécessaires pour statuer sur la demande d'assistance judiciaire ainsi qu'une autorisation du recourant de consulter ses dossiers médicaux. Le tribunal a reçu ces documents le 8 avril 2011 et a le jour même requis des rapports au sens de l'<ref-law> des EPV et du service médical s'étant occupé du recourant. Aucun manque de diligence ne peut être reproché quant à cette période.
5.5.2 L'autorité précédente a admis une période d'inactivité du 28 avril 2011 au 19 juillet 2011 qu'elle a justifiée par l'attente du rapport médical nécessaire au traitement de la requête (ordonnance entreprise, p. 12). Une telle attente, sans relance, ne se concilie cependant guère avec les exigences découlant de l'<ref-law> et l'examen des circonstances d'espèce ne permet pas de l'expliquer.
5.5.3 Le recourant reproche au tribunal de l'application des peines et mesures d'avoir attendu de connaître le sort donné à ses recours. Il y voit notamment une violation, arbitraire, de l'<ref-law>.
Le CPP n'est pas directement applicable à la procédure de libération conditionnelle (cf. <ref-law>). Le recourant n'expose au surplus pas conformément aux exigences posées par l'<ref-law> - et donc de manière recevable - dans quelle mesure l'<ref-law>, en tant que droit cantonal supplétif éventuel, aurait été arbitrairement violé. Le grief de violation de cette disposition est partant irrecevable. Quoi qu'il en soit, le tribunal de l'application des peines et mesures a attendu, pour convoquer et entendre le recourant, que sa décision du 19 juillet 2011 refusant les autres nombreuses mesures d'instruction requises par le recourant soit définitive. Il a expliqué cette attente en arguant que le recourant devait être entendu au terme de la procédure probatoire afin qu'il puisse faire valoir son point de vue sur toutes les pièces du dossier (décision du 19 juillet 2011, ch. 3 p. 5; <ref-law>). Un tel motif est justifié. Au surplus, il s'agissait d'une décision incidente non susceptible de recours cantonal immédiat (ordonnance du 31 août 2011, p. 11) et en principe pas non plus de recours immédiat auprès du Tribunal fédéral (arrêt 6B_661/2011 du 7 février 2012 consid. 3.2). Le recourant aurait dû s'en rendre compte en procédant à une analyse consciencieuse de la recevabilité des moyens qu'il souhaitait soulever.
S'agissant du recours formé le 20 avril 2011, il n'apparaît pas que l'autorité de première instance ait suspendu la procédure pour ce motif. Le grief tombe donc à faux.
Quant au recours formé le 27 juillet 2011, ce dernier a été instruit avec celui du 28 juillet 2011 contre la décision du 19 juillet 2011. La suspension restait donc justifiée par le traitement de ce dernier recours.
5.5.4 Le 7 mars 2012, le tribunal de l'application des peines et mesures a reçu l'arrêt du Tribunal fédéral 6B_661/2011 du 7 février 2012 - jugeant irrecevable le recours formé à l'encontre du refus de complément d'instruction. Le lendemain, il a requis du service médical des EPO un rapport actualisé. Ce service a répondu, par courrier du 13 mars 2012, reçu le 16 mars 2012, indiquant que l'état du recourant était stable et qu'il n'avait rien à ajouter à son rapport actualisé du 22 novembre 2011. Le tribunal de l'application des peines et mesures n'a toutefois entendu le recourant que le 23 avril 2012, soit près de six semaines plus tard. Rien dans l'ordonnance entreprise, ni le dossier ne justifie un tel délai. Celui-ci est d'autant plus inexplicable qu'il intervient bien plus d'une année après le prononcé de la mesure en août 2010 et une année après la réception des requêtes de libération conditionnelle jointes au courrier du 25 mars 2011.
5.5.4 Le 7 mars 2012, le tribunal de l'application des peines et mesures a reçu l'arrêt du Tribunal fédéral 6B_661/2011 du 7 février 2012 - jugeant irrecevable le recours formé à l'encontre du refus de complément d'instruction. Le lendemain, il a requis du service médical des EPO un rapport actualisé. Ce service a répondu, par courrier du 13 mars 2012, reçu le 16 mars 2012, indiquant que l'état du recourant était stable et qu'il n'avait rien à ajouter à son rapport actualisé du 22 novembre 2011. Le tribunal de l'application des peines et mesures n'a toutefois entendu le recourant que le 23 avril 2012, soit près de six semaines plus tard. Rien dans l'ordonnance entreprise, ni le dossier ne justifie un tel délai. Celui-ci est d'autant plus inexplicable qu'il intervient bien plus d'une année après le prononcé de la mesure en août 2010 et une année après la réception des requêtes de libération conditionnelle jointes au courrier du 25 mars 2011.
5.6 Au regard des différentes phases de la procédure analysées ci-dessus, plus spécifiquement de certaines périodes d'inactivité non justifiée (cf. supra consid. 5.5.2 et 5.5.4), ainsi que du temps écoulé entre le prononcé de la mesure et celui où il a été statué sur la libération (21 mois) respectivement du temps écoulé depuis la réception des demandes de libération (14 mois), il apparaît que la durée globale mise pour statuer consacre en l'occurrence une violation de l'<ref-law>. Cette violation ne conduit pas en elle-même à l'annulation de l'ordonnance attaquée ni ne constitue un motif de prononcer la libération conditionnelle, les conditions pour l'octroi de celle-ci étant autonomes. Toutefois, cette violation est constatée dans le présent considérant et le recourant bénéficiera d'une dispense de frais de justice et obtiendra une indemnité pour ses frais de défense (cf. <ref-ruling> consid. 2.2 p. 121). De même, dans le cadre du renvoi (supra, consid. 3.2.2), l'autorité cantonale dispensera le recourant des frais judiciaires et lui allouera une indemnité à titre de dépens pour la procédure cantonale.
6. Le recourant se plaint par ailleurs que ses demandes de libération conditionnelle, adressées dès le 20 octobre 2010 à la direction de la Prison des Iles et au Juge du Tribunal des districts de Martigny et Saint-Maurice, n'aient pas été transmises à l'autorité compétente. Il relève que l'art. 7 al. 3 de la loi valaisanne du 6 octobre 1976 sur la procédure et la juridiction administratives (LPJA/VS; RS/VS 172.6) imposait à l'autorité saisie d'une affaire, qui s'estime incompétente, de transmettre sans délai celle-ci à l'autorité compétente et d'en aviser les intéressés. Il y voit la justification d'une indemnité fondée sur l'art. 5 par. 4 et 5 CEDH.
Ce moyen n'a pas été examiné par l'autorité précédente, sans que le recourant n'invoque ni ne démontre qu'elle aurait commis par là un déni de justice. Conformément au principe de l'épuisement préalable des voies de droit cantonal (<ref-law> et cf. <ref-ruling> consid. 2 p. 639 s.), il est irrecevable.
7. Le recourant requiert une indemnisation de 50'000 fr. fondée sur l'art. 5 par. 5 CEDH (recours, en particulier ch. 29.3 p. 11).
Cette disposition prévoit une réparation dans les cas de détention contraires à l'art. 5 par. 1 à 4 CEDH. Le recourant n'a pas, de manière recevable, démontré une telle violation (supra consid. 4). Il ne saurait partant obtenir une réparation en vertu de l'art. 5 par. 5 CEDH.
8. Dans son mémoire, le recourant se réfère à diverses autres dispositions légales, constitutionnelles ou conventionnelles. Il ne formule toutefois à leur égard aucun grief qui serait recevable sous l'angle de l'art. 42 al. 2, respectivement 106 al. 2 LTF.
9. En conclusion, le recours doit être admis partiellement, l'ordonnance du 9 juillet 2012 annulée et la cause renvoyée à l'autorité précédente pour nouvelle instruction et nouvelle décision dans le sens des considérants. Le recours est rejeté pour le surplus, dans la mesure de sa recevabilité.
Conformément à ce qui a été indiqué précédemment (supra ad consid. 5.6), il se justifie d'accorder une indemnité de dépens à l'avocat du recourant à la charge du canton du Valais (art. 68 al. 1 et 2 LTF) et de renoncer à percevoir des frais judiciaires pour la présente procédure (<ref-law>). La requête d'assistance judiciaire est partant sans objet.
II. Recours 6B_471/2012 contre l'arrêt du 18 juin 2012
10. Le recourant requiert la production des dossiers ayant abouti aux deux décisions contestées. Dans la mesure où ces dossiers ont été versés dans chaque procédure et que celles-ci sont jointes, sa requête est satisfaite.
11. Le recourant se plaint du refus de la direction des EPV, confirmé par l'autorité de recours, d'entrer en matière sur ses requêtes concernant "le choix de l'établissement et ses conditions de détention". Il conteste également le rejet de sa requête d'assistance judiciaire.
12. Il ressort de la décision du 21 avril 2011 de la direction des EPV que le recourant a requis son placement à l'hôpital psychiatrique de Malévoz ou à la colonie pénitentiaire de Crêtelongue. A l'instar de la direction des EPV, l'autorité de recours a considéré que la question de la détermination du choix de l'établissement d'exécution d'un traitement institutionnel au sens de l'<ref-law> constituait un acte matériel, ne modifiant pas les droits et obligations du recourant au sens de l'art. 5 LPJA/VS, de sorte que l'autorité n'avait pas à rendre une décision sur ce point. L'autorité de recours a en outre relevé ne pas voir quelle actualité présentait encore, dès le transfert du recourant de la Prison des Iles aux EPO, la demande d'une décision sur un placement à Crêtelongue ou à l'hôpital psychiatrique de Malévoz.
13. Le Tribunal fédéral examine d'office la recevabilité des recours qui sont déposés devant lui (<ref-ruling> consid. 1 p. 472). L'arrêt attaqué porte sur l'exécution d'une mesure, de sorte que la voie du recours en matière pénale est ouverte (cf. <ref-law>). La recevabilité du recours en matière pénale suppose un intérêt juridique à l'annulation de la décision entreprise (<ref-law>). Cet intérêt doit être actuel et pratique (<ref-ruling> consid. 1.3 p. 276), soit exister tant au moment du dépôt du recours qu'à celui où l'arrêt est rendu (<ref-ruling> consid. 4.2 p. 299). Un intérêt général ou de fait est insuffisant (<ref-ruling> consid. 2.3 p. 230 s.). Le détenu n'a ainsi en principe pas le droit de choisir le lieu de l'exécution de sa peine (arrêts 6B_602/2012 du 18 décembre 2012 consid. 1; 6B_660/2011 du 23 février 2012 consid. 1.2).
14.
14.1 Le recourant se plaint d'avoir à exécuter sa mesure aux EPO plutôt que dans un autre établissement carcéral, notamment à l'établissement pénitentiaire de Crêtelongue. Comme exposé ci-dessus (ad consid. 13 in fine), le recourant ne dispose pas d'un intérêt à choisir le lieu d'exécution. Le recourant se plaint certes des conditions dans lesquelles la mesure est exécutée. Ses critiques portent toutefois principalement sur ses conditions avant son transfert aux EPO, le 3 mars 2011. Elles ne sont dès lors pas propres à démontrer un intérêt actuel à contester l'arrêt cantonal. Le recourant évoque aussi ne pas avoir été placé aux EPO dans une section de soins psychiatrique. Il n'apparaît toutefois pas que le traitement nécessaire ne soit pas assuré et ce par du personnel qualifié. L'ordonnance du 9 juillet 2012, p. 6, indique ainsi que le recourant suit aux EPO, ce depuis le 22 novembre 2011 au moins - date du rapport médical cité -, un traitement psychiatrique intégré associant des entretiens psychothérapeutiques à un traitement psychopharmacologique. Dans ces conditions et faute de tout autre élément, on ne saurait considérer que le recourant a un intérêt juridique actuel à requérir son transfert dans un autre établissement pénitentiaire. A cet égard, son recours est irrecevable.
14.2 Le recourant a par ailleurs sollicité de la direction des EPV son transfert des EPO à l'hôpital psychiatrique de Malévoz. On comprend ainsi que le recourant a requis son passage d'un milieu carcéral à un milieu hospitalier, autrement dit son transfert en milieu ouvert au sens de l'<ref-law>, l'hôpital de Malévoz n'ayant pas de section permettant d'exécuter un traitement hospitalier en milieu fermé au sens de l'<ref-law>. En ce sens, le recourant a formé auprès de la direction des EPV une requête similaire à celle du 25 mars 2011 auprès du tribunal de l'application des peines et mesures (supra let. Ba) dont il a été question dans la cause 6B_517/2012. Il avait en effet sollicité dans dite demande du 25 mars 2011, à titre subsidiaire, son transfert en milieu ouvert. Un telle requête de transfert d'un milieu fermé en milieu ouvert relève dans le canton du Valais du Juge de l'application des peines et mesures (cf. art. 5 de la loi valaisanne du 14 septembre 2006 d'application du code pénal; LACP/VS; RS/VS 311.1; décision du 24 mai 2012 p. 16). Dans ces conditions, on ne voit pas que le recourant dispose d'un intérêt juridique actuel à l'annulation de la décision attaquée au regard de la procédure parallèle où cette question devra le cas échéant être traitée (supra consid. 3.2.2 in fine). Le recours est dès lors irrecevable sur ce point également.
14.3 Pour le surplus, l'autorité précédente n'a pas réexaminé la décision d'incompétence rendue par la direction des EPV concernant la question de la levée de la mesure, sans que le recourant ne se plaigne ici de déni de justice sur ce point. Elle n'a pas non plus rendu ou confirmé de décisions d'irrecevabilité sur d'autres "conditions de détention", respectivement traité celles-ci. Faute de respecter le principe de l'épuisement préalable des voies de droit cantonales (<ref-law>; <ref-ruling> consid. 2.1 p. 93), le grief consistant à se plaindre du refus des autorités cantonales d'entrer en matière sur ses requêtes concernant d'autres conditions de détention que celles examinées ci-dessus ad consid. 14.1 et 14.2 est dès lors irrecevable.
15. A l'égard du refus d'assistance judiciaire, le recourant ne cherche pas à établir de manière conforme aux exigences de l'<ref-law> en quoi le droit cantonal aurait été appliqué de manière arbitraire ou l'art. 29 al. 3 Cst. violé mais se contente de dire que son recours cantonal n'était pas dépourvu de chances de succès. Insuffisamment motivé, son grief est irrecevable.
16. Le recours est ainsi irrecevable. Dès lors qu'il était dépourvu de chances de succès, l'assistance judiciaire doit être refusée (<ref-law>). Le recourant supporte les frais, qui seront fixés à 800 fr. au vu de sa situation financière défavorable (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Les causes 6B_471/2012 et 6B_517/2012 sont jointes.
2. Le recours 6B_471/2012 est irrecevable.
3. Le recours 6B_517/2012 est partiellement admis, l'ordonnance attaquée est annulée et la cause est renvoyée à l'autorité cantonale pour nouvelle décision. Pour le surplus, le recours est rejeté dans la mesure où il est recevable.
4. Les demandes d'assistance judiciaire sont rejetées dans la mesure où elles ne sont pas sans objet.
5. Les frais judiciaires, arrêtés à 800 fr., sont mis à la charge du recourant.
6. Le canton du Valais versera à l'avocat du recourant une indemnité de 3'000 fr. à titre de dépens pour la procédure devant le Tribunal fédéral.
7. Le présent arrêt est communiqué aux parties, au Président de la Cour de droit public et à la Chambre pénale du Tribunal cantonal du canton du Valais.
Lausanne, le 21 janvier 2013
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président: Mathys
La Greffière: Cherpillod