Faits: A. Par jugement du 22 avril 2013, le Tribunal d'application des peines et des mesures genevois (ci-après : TAPEM) a rejeté la demande de libération conditionnelle de l'internement de X._. B. Statuant sur le recours formé par X._, la Chambre pénale de recours de la Cour de justice genevoise l'a rejeté par arrêt du 28 juin 2013. Il en ressort les éléments suivants. B.a. Le 3 novembre 1998, la Cour d'assises genevoise a condamné X._, né en 1954, pour tentative de viol avec cruauté et rupture de ban à une peine de 5 ans de réclusion, suspendu cette peine au profit d'un internement et ordonné un traitement psychiatrique, mesures fondées sur l'ancien art. 43 ch. 1 al. 2 CP. B.b. Le parcours judiciaire de X._, débuté à l'adolescence déjà, comporte plusieurs infractions contre l'intégrité sexuelle. En 1969, il est signalé à la Brigade des moeurs pour exhibitionnisme, s'étant masturbé devant des passants. En 1970, il est arrêté pour s'être introduit dans une villa, s'être déshabillé et avoir pénétré dans la chambre de la propriétaire de celle-ci « dans le but de faire des cochonneries avec elle ». En 1974, il est condamné par le Tribunal correctionnel de Thonon à 3 mois d'emprisonnement pour outrage à la pudeur, s'étant dévêtu totalement à plusieurs reprises devant des tiers, notamment des fillettes âgées de respectivement 6 et 12 ans. En 1976, il s'est rendu coupable de violation de domicile, lésions corporelles simples et tentative de viol et a été condamné à 2 ans d'emprisonnement. En 1982, en France, il a écopé de 4 ans de prison pour avoir pratiqué des attouchements sur une fillette de 10 ans. En 1987, il est condamné à Genève à 8 ans de réclusion pour deux viols, étant précisé que X._ a toujours contesté avoir commis ces infractions. B.c. L'état de santé psychique de X._ a été examiné à réitérées reprises depuis 1977 et a fait l'objet de plusieurs expertises. A la suite de son internement en 1998, l'état de santé psychique de X._ a été périodiquement examiné par le Conseil de surveillance psychiatrique (ci-après : CSP) entre septembre 2000 et octobre 2006. Le CSP a relevé que X._ conservait un discours projectif, s'estimant victime de la justice et demeurait dans le déni des faits à l'origine de ses deux dernières condamnations. Son discours, de type monodique, était centré sur un illusoire succès judiciaire. A l'exception d'un suivi entre 1998 et 2001 consacré à des problèmes d'ordre existentiel liés à la souffrance résultant de son incarcération et à l'expression de ses revendications juridiques, il s'était refusé à tout traitement psychothérapeutique, au motif qu'un tel traitement équivaudrait, selon lui, à une reconnaissance de sa culpabilité et de sa maladie. Dans le cadre de la présente cause, X._ a été soumis à une nouvelle expertise réalisée par le Dr Y._, psychiatre-psychothérapeute, qui a rendu son rapport le 15 novembre 2012. Cet expert a indiqué avoir utilisé plusieurs outils d'évaluation du risque de réitération pour les comportements violents et les actes délictueux de nature sexuelle. Selon une évaluation comprenant à la fois le HCR-20 mais également une version plus spécifique pour les comportements sexuels violents (SVR-20), complétée d'une échelle de psychopathie de HARE, mais également des échelles Statique-99 et Stable-2007, le risque de réitération de comportements sexuels et violents, évalués à la lueur de tels instruments, allait dans le sens d'un risque de degré moyen à élevé. L'expert a posé le diagnostic de trouble mixte de la personnalité à caractéristique paranoïaque mais également avec des éléments narcissiques-pervers et une composante psychopathique, accompagné d'un trouble mental organique dû à une lésion ou un dysfonctionnement cérébral ou à une affection physique sans précision, ainsi que d'une immaturité du développement psycho-sexuel. Cette appréciation ne s'écartait pas fondamentalement des expertises judiciaires précédentes. L'expertisé présentait une rigidité mentale majeure, des tendances rancunières tenaces cristallisées actuellement sur différents « objets persécuteurs » notamment la justice et les médecins, ainsi qu'une image grandiose de lui-même, caractérisée par la toute-puissance et une absence de réponse aux tentatives de recadrage de l'évaluateur. Sa manière de tenter de dissimuler et de minimiser une partie des faits en sa défaveur était un écueil pour mener à bien l'expertise. Cette tendance s'exprimait aussi dans la prise en compte limitée et minimalisée du vécu de la victime, sur qui il paraissait rejeter la responsabilité de ses actes. De manière générale, l'expertisé ne semblait pas parvenir à dissocier excitation sexuelle et violence. Dans un passage consacré au déni, l'expert a précisé que celui-ci n'était ni un symptôme d'une maladie, ni un trouble psychique, mais un phénomène classé dans les mécanismes de défense inconscients du psychisme, les hypothèses étant nombreuses dans la façon dont le déni s'exprimait chez l'expertisé. Ce n'était toutefois pas ce seul déni qui était à l'origine de sa stagnation, mais sa personnalité dans son ensemble. L'expert a constaté que les traitements entrepris depuis 2008 n'avaient pas engendré d'évolution de l'état de santé de l'expertisé en ce qui concernait le volet psychiatrique. Il n'y avait pas eu non plus d'évolution en ce qui concernait la prise de conscience de la gravité de ses actes, le repentir, le vécu de la mesure, l'intégration de la sanction et l'adhésion au traitement. En raison de la personnalité de l'expertisé, des circonstances dans lesquelles il avait commis l'infraction et de son vécu, il restait toujours sérieusement à craindre qu'il ne commît de nouvelles infractions portant gravement atteinte à l'intégrité physique, psychique ou sexuelle d'autrui. L'expertisé présentait avant tout un grave trouble de la personnalité conjugué à une immaturité du développement psycho-sexuel et souffrait de probables séquelles de traumatismes cranio-cérébraux. Étant donné les caractéristiques des troubles (et notamment la dimension psychopathique, une possible touche de lésion cérébrale) la pathologie de l'expertisé, prise dans son ensemble, se trouvait également à la frontière de l'appellation de trouble mental grave. Aussi, un internement demeurait nécessaire vu l'absence d'évolution et les facteurs de risque de réitération. Une prise en charge psychiatrique spécialisée dans le domaine forensique avait été instaurée à plusieurs reprises, sans succès jusqu'à ce jour. Les échecs répétés desdites prises en charge ne pouvaient qu'aller dans le sens d'un pronostic de plus en plus défavorable en ce qui concernait leurs chances de pouvoir favoriser une évolution de l'expertisé. Plus le temps passait, plus ce genre de mesure avait tendance à devenir « une vue de l'esprit », les modalités d'application étant particulièrement limitées. B.d. Selon un rapport du 16 décembre 2009, le Service médical des Etablissements de la plaine de l'Orbe (ci-après : EPO) a relaté que, depuis son arrivée aux EPO, X._ bénéficiait d'un suivi thérapeutique à quinzaine mené par deux psychologues. Le patient venait aux entretiens et investissait bien l'espace qui lui était proposé. Il souhaitait une psychothérapie pour parler de lui-même, comprendre ce qui s'était passé dans son existence, tout en précisant qu'il ne souhaitait pas une thérapie centrée sur la reconnaissance des faits. Dès lors, il profitait du suivi pour parler de son histoire personnelle, notamment d'événements de son enfance particulièrement douloureux et relevait l'aspect bénéfique de ce travail. Le 11 septembre 2010, ce même service a rendu un nouveau rapport. X._ bénéficiait d'entretiens psychothérapeutiques à quinzaine jusqu'au mois de juin 2010 et mensuels depuis cette date, sans recevoir de médication psychotrope. Il venait régulièrement aux entretiens qui lui étaient proposés et, lors des derniers mois, les avait utilisés principalement dans le but d'expliquer aux thérapeutes les injustices qu'il ressentait et d'exposer sa version des faits de l'infraction. L'alliance thérapeutique était bonne et l'objectif du traitement était de permettre au patient de mieux cerner en quoi consistait un travail introspectif. Les perspectives étaient que le patient pût se dégager de son besoin de se justifier sur les faits délictuels ou juridiques afin de pouvoir se pencher et s'interroger sur son fonctionnement psychique. A ses débuts, le travail thérapeutique avait été vécu comme bénéfique par le patient mais progressivement les thérapeutes avaient constaté que cet échange, sans contester nullement l'effet bénéfique que pouvait revêtir le fait de parler d'événements traumatiques de l'enfance, n'avait pas permis un authentique travail introspectif. Le 27 janvier 2011, les thérapeutes de X._ ont précisé que celui-ci préférait que le contenu de ses thérapies reste confidentiel. En date du 22 août 2011, le service médical des EPO a confirmé que X._ n'était plus suivi sur le plan psychiatrique ou psychologique et que celui-ci n'avait pas autorisé les soignants à faire état du contenu de l'entretien qu'il avait eu avec eux à la suite de la demande du rapport du Service de l'application des peines et des mesures (ci-après : SAPEM). B.e. Par écrits des 5 mars 2010 et 26 juillet 2011, la Commission d'évaluation de la dangerosité a estimé que X._ présentait un caractère dangereux pour la collectivité. Quant au SAPEM, il s'est prononcé par préavis du 15 août 2011 en faveur du maintien de l'internement. B.f. Lors de l'audience du 29 novembre 2011, X._ a déclaré avoir mis fin à son suivi thérapeutique au mois de septembre 2010, après avoir pris connaissance du rapport du 11 septembre 2010 rendu par ses médecins. A la suite de ce rapport, il avait déposé une plainte pénale laquelle avait été classée. Cette plainte était motivée par le fait que le suivi thérapeutique s'inscrivait dans le cadre d'une démarche volontaire personnelle et non dans le cadre de la mesure pénale d'internement. S'il n'y avait pas eu ce problème de violation du secret professionnel, il aurait volontiers continué cette thérapie. L'objectif de celle-ci était de mieux comprendre son fonctionnement personnel. Il a confirmé qu'il n'y avait pas eu de travail orienté vers une remise en question destinée à comprendre les faits pour lesquels il avait été condamné dans la mesure où il les contestait. Il aurait voulu suivre une thérapie volontaire et non liée à l'internement compte tenu du fait qu'il n'y avait aucune obligation de soin liée à l'internement. C. X._ forme un recours en matière pénale au Tribunal fédéral contre l'arrêt du 28 juin 2013. Il conclut, sous suite de frais et dépens, principalement à sa réforme en ce sens que la libération conditionnelle de l'internement est octroyée, selon les modalités fixées à dire de justice. Subsidiairement, il conclut à la réforme en ce sens que la mesure d'internement est remplacée par une mesure thérapeutique institutionnelle, plus subsidiairement un traitement ambulatoire. Encore plus subsidiairement, il conclut à l'annulation de l'arrêt attaqué et au renvoi de la cause à l'autorité inférieure. Il requiert par ailleurs l'assistance judiciaire.