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 <ref-law>.
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.

Considérant en droit:
1.
1.1.
Le Tribunal fédéral conduit son raisonnement sur la base des faits établis par la juridiction précédente (<ref-law>). Il ne peut s'en écarter que si ces faits ont été établis de façon manifestement inexacte - à savoir arbitraire (<ref-ruling> consid. 5.1 p. 356). Le grief d'arbitraire doit être invoqué et motivé de manière précise (<ref-law>). Le recourant doit exposer, de manière détaillée et pièces à l'appui, que les faits retenus l'ont été d'une manière absolument inadmissible, et non seulement discutable ou critiquable. Il ne saurait se borner à plaider à nouveau sa cause, contester les faits retenus ou rediscuter la manière dont ils ont été établis comme s'il s'adressait à une juridiction d'appel (<ref-ruling>). Le Tribunal fédéral n'entre pas en matière sur les critiques de nature appellatoire (<ref-ruling> consid. 5.1 p. 356 ; <ref-ruling> consid. 6 p. 397).
1.2. Le recourant débute ses écritures par une présentation personnelle des faits. Dans la mesure où il s'écarte des faits retenus par la cour cantonale sans démontrer que ceux-ci auraient été établis de manière arbitraire, son exposé est appellatoire, partant irrecevable.
2.
Le recourant conteste l'évaluation faite de sa dangerosité et du risque de récidive. Il requiert que sa libération conditionnelle de l'internement soit ordonnée.
2.1. Selon l'<ref-law>, l'auteur est libéré conditionnellement dès qu'il est à prévoir qu'il se conduira correctement en liberté. Le délai d'épreuve est de deux à cinq ans. Une assistance de probation peut être ordonnée et des règles de conduite peuvent lui être imposées pour la durée de la mise à l'épreuve.
2.1.1. La libération conditionnelle de l'internement au sens de l'<ref-law> dépend d'un pronostic favorable. L'examen de ce pronostic est effectué de manière plus stricte que lors de l'examen de la même question concernant les mesures thérapeutiques institutionnelles (cf. <ref-law>). La libération conditionnelle aura lieu s'il est « à prévoir », c'est-à-dire s'il existe une forte probabilité que le condamné se conduise bien en liberté. La garantie de la sécurité publique doit être assurée avec une probabilité aussi élevée que les enjeux soulevés par la libération conditionnelle, sans qu'une sécurité absolue ne puisse jamais être tout à fait garantie (<ref-ruling> consid. 2.1.1 p. 167 et les références citées). La condition de la prévisibilité d'une conduite correcte en liberté doit être appréciée par rapport aux seules infractions énumérées à l'<ref-law>. Les autres comportements, qui n'entrent pas dans les prévisions de cette dernière disposition, ne sont pas pertinents (<ref-ruling> consid. 2.1.1 p. 167 et l'arrêt cité).
2.1.2. Le pronostic doit être posé en tenant compte du comportement du condamné dans son ensemble et plus particulièrement de sa collaboration face aux traitements prescrits par les médecins, de la prise de conscience des actes à la base de sa condamnation, de ses aptitudes sociales et, notamment, de ses capacités à vivre en communauté et à résoudre des conflits potentiels. Il est difficile d'évaluer, à sa juste valeur, la dangerosité d'un détenu, dès lors que celui-ci évolue précisément dans un milieu conçu aux fins de le neutraliser (<ref-ruling> consid. 2.1.2 et les références citées).
2.1.3. En matière de pronostic, le principe « in dubio pro reo » ne s'applique pas (<ref-ruling> consid. 2a p. 4; <ref-ruling> consid. 2a p. 114).
2.2. L'<ref-law> précise que l'autorité compétente prend la décision sur l'éventuelle libération conditionnelle en se fondant sur un rapport de la direction de l'établissement, une expertise indépendante au sens de l'<ref-law>, l'audition d'une commission au sens de l'<ref-law> et l'audition de l'auteur.
S'agissant de l'expertise, comme tous les autres moyens de preuve, celle-ci est soumise à la libre appréciation du juge. Ce dernier ne peut cependant pas s'écarter d'une expertise sans motifs pertinents. Il doit examiner, en se fondant sur les autres moyens de preuve administrés et sur les arguments des parties, si de sérieuses objections font obstacle au caractère probant des conclusions de l'expertise. En se fondant sur une expertise non concluante, le juge peut tomber dans l'arbitraire (<ref-ruling> consid. 3.2 p. 547 s.). Tel peut être le cas si l'expert n'a pas répondu aux questions posées, si ses conclusions sont contradictoires ou si, de toute autre façon, l'expertise est entachée de défauts à ce point évidents et reconnaissables, même sans connaissances spécifiques, que le juge ne pouvait tout simplement pas les ignorer. Il n'appartient pas au Tribunal fédéral de vérifier si toutes les affirmations de l'expert sont exemptes d'arbitraire; sa tâche se limite bien plutôt à examiner si l'autorité précédente pouvait, sans arbitraire, se rallier au résultat de l'expertise (arrêt 9C_717/2011 du 25 juin 2012 consid. 5.1).
2.3. En résumé, la cour cantonale, se ralliant aux conclusions de l'expertise du 15 novembre 2012, a retenu que la dangerosité du recourant était très clairement établie, en lien avec des infractions à l'intégrité sexuelle, voire corporelle, et que sa remise en liberté ferait courir un danger grave à la population. Elle a ainsi retenu que les conditions pour une libération conditionnelle de l'internement n'étaient pas réalisées.
2.4. Le recourant soutient que l'expert et les juges n'auraient pas suffisamment tenu compte de son âge, de son état de santé actuel et de son bon comportement en détention, facteurs permettant de diminuer notablement sa dangerosité.
2.4.1. A titre liminaire, il sera relevé que l'expert s'est fondé sur des outils statistiques et sur des facteurs cliniques pour effectuer son expertise. Après un exposé détaillé et argumenté des éléments dont il a tenu compte et de leur influence, il a abouti à la conclusion que le risque de récidive était moyen à élevé.
2.4.2. S'agissant de son âge, le recourant fait grief à l'expert d'avoir indiqué que l'âge était considéré comme un facteur abaissant le score de dangerosité, sans que l'on puisse toutefois constater d'effet sur les conclusions de l'expert qui, au demeurant, aurait omis de citer ce critère dans sa réponse.
Il ressort de l'arrêt entrepris que, lors de l'audience du 24 janvier 2013, l'expert a indiqué avoir omis de reprendre cet élément dans sa réponse spécifique en fin d'expertise, mais qu'il y était fait référence dans le corps de l'expertise. Selon le rapport d'expertise du 15 novembre 2012 (p. 33), ce facteur a été pris en compte dans le cadre de l'évaluation fondée sur l'échelle Statique-99, cet élément abaissant le score de l'expertisé d'un point, ce qui a été confirmé par l'expert lors de son audition. Dès lors, l'expert a tenu compte de l'âge du recourant qui n'était que l'un des critères parmi d'autres dans son évaluation. Son effet n'avait pas à se refléter particulièrement dans ses réponses en fin d'expertise, étant précisé que celles-ci sont une synthèse de l'expertise et en reprennent les conclusions. A tout le moins, le recourant ne démontre pas en quoi il était manifestement insoutenable de conclure à un risque de récidive moyen à élevé malgré son âge, dont on soulignera qu'il n'était que de 58 ans au moment de l'expertise (105 al. 2 LTF). Le grief du recourant est infondé dans la mesure où il est recevable.
2.4.3. Le recourant soutient que son état de santé actuel diminuerait le risque de récidive dès lors que les infractions dont on craindrait la réalisation seraient des atteintes à l'intégrité sexuelle qui impliqueraient, pour qu'elles puissent être commises, une certaine force physique et une certaine violence.
Outre que le recourant ne démontre pas quelle serait l'influence de son état de santé sur sa force physique, il fait fi du fait qu'il a été condamné pour avoir tenté de violer une femme alors qu'il la menaçait d'un couteau. Muni d'une telle arme, la force physique nécessaire à la commission de l'infraction est limitée. Cet élément ne permet pas de démontrer qu'il était insoutenable de retenir un risque de récidive moyen à élevé malgré la prétendue baisse de la force physique du recourant. Supposé recevable, le grief du recourant est infondé.
2.4.4. Contrairement à ce que soutient le recourant, l'expert a tenu compte de son bon comportement en détention. A cet égard, il a relevé que celui-ci n'était pas incompatible avec sa pathologie. Au contraire, sa psychopathologie, qui comportait des aspects de séduction et de manipulation, pouvait tout à fait rendre compte du fait que, considéré sous certains aspects, son comportement pouvait s'avérer très adapté dans le cadre carcéral. Le rapport faisant état du bon comportement du recourant en détention était pondéré notamment par le fait qu'il y était également indiqué que le recourant, qui avait d'abord été un détenu exemplaire dans son attitude et dans son travail, avait peu à peu cherché à acquérir vis-à-vis de ses pairs comme du personnel de la prison la reconnaissance d'un statut particulier, supérieur à celui des autres. Le refus du personnel pénitentiaire d'accéder à ses doléances avait entraîné un renoncement progressif à exercer correctement son travail, puis au final à le bâcler (105 al. 2 LTF; rapport d'expertise p. 24).
2.4.5. En définitive, le recourant ne cite aucun élément qui serait propre à démontrer que les conclusions de l'expertise seraient insoutenables, ni qu'il était arbitraire de s'y rallier comme la cour cantonale l'a fait. Ses critiques sont infondées dans la mesure où elles sont recevables.
2.5. Le recourant soutient qu'il serait faux de retenir, comme l'a fait la cour cantonale, que la gravité des délits qu'il a commis irait en s'accroissant, dès lors qu'il a été condamné en 1987 pour deux viols et en 1998 pour une tentative de viol, cette infraction étant clairement moins grave.
Outre que le recourant ignore que c'est en raison du fait que sa victime s'est débattue avec suffisamment de véhémence alertant ainsi un passant qu'elle a pu lui échapper et que le viol s'est arrêté au stade de la tentative, il méconnaît également ses nombreux autres antécédents. C'est à la lumière de l'ensemble de son parcours criminel que l'accroissement de la gravité de ses comportements prend tout son sens. On se bornera à rappeler que le parcours judiciaire du recourant, débuté à l'adolescence déjà, commence par de l'exhibitionnisme, se poursuit par l'introduction dans une villa dans l'intention de violer une femme, puis par une condamnation pour outrage à la pudeur et une autre pour violation de domicile, lésions corporelles simples et tentative de viol. Il continue avec des attouchements sur une fillette de 10 ans, puis une condamnation pour deux viols et se termine par une condamnation pour tentative de viol dans les circonstances décrites ci-dessus. Au regard de ces éléments, il n'était pas inexact, encore moins arbitraire, de retenir que la gravité des infractions commises par le recourant est allée crescendo.
2.6. Le recourant rappelle que l'infraction qui a mené à son internement n'a pas été consommée. Dans la mesure où il cherche à revenir sur les circonstances ayant conduit à sa condamnation définitive et exécutoire, tout en se défendant de le faire, son grief est irrecevable. Pour le surplus, et comme il le souligne lui-même, la tentative est suffisante pour le prononcé d'un internement. Quant à l'octroi de la libération conditionnelle, elle dépend du pronostic formulé s'agissant du comportement en liberté du condamné et non du stade de réalisation de l'infraction à l'origine de l'internement. La cour cantonale pouvait donc ignorer cet élément dans l'examen du pronostic.
2.7. Le recourant ne cite en définitive aucun élément important, propre à modifier le pronostic, qui aurait été omis ou pris en considération à tort. Au vu des troubles psychiatriques dont souffre le recourant, du pronostic de dangerosité posé par l'expert et de l'immobilisme de la situation psychiatrique du recourant, la cour cantonale pouvait, sans excès, ni abus du pouvoir d'appréciation, refuser de libérer conditionnellement le recourant de l'internement.
2.8. Le recourant se réfère au principe de proportionnalité dont il soutient qu'il doit être pris en compte dans l'établissement du pronostic, en particulier en raison du fait qu'il a été condamné à une peine de 5 ans et qu'il est interné depuis 15 ans, ce d'autant plus que l'infraction considérée n'a été réalisée qu'au stade de la tentative.
2.8.1. Toute sanction pénale qui restreint un droit fondamental doit respecter le principe de proportionnalité (art. 36 al. 2 et 3 Cst.). En matière de mesure, ce principe a été concrétisé à l'<ref-law>. Aux termes de cette disposition, le prononcé d'une mesure suppose que l'atteinte aux droits de la personnalité qui en résulte pour l'auteur ne soit pas disproportionnée au regard de la vraisemblance qu'il commette de nouvelles infractions et de leur gravité. Ce principe vaut tant pour le prononcé d'une mesure que pour son examen postérieur. Concrètement, il convient de procéder à une pesée des intérêts divergents en présence, c'est-à-dire entre la gravité du danger, que la mesure cherche à éviter, et l'importance de l'atteinte aux droits de la personne concernée inhérente à la mesure. Une mesure disproportionnée ne doit pas être ordonnée, ni maintenue (arrêt 6B_109/2013 du 19 juillet 2013 consid. 4.4.1 et les références citées).
Le principe de proportionnalité exige que la sécurité publique et le droit à la liberté de l'interné soient mis en balance l'un avec l'autre. Dans les cas de placements de très longue durée, le droit à la liberté de l'interné gagne du poids. Le principe de proportionnalité exerce à cet égard la même fonction de délimitation que le principe de culpabilité (arrêt 6B_109/2013 du 19 juillet 2013 consid. 4.4.2; cf. MARIANNE HEER, in Basler Kommentar, Strafrecht I, 3 e éd. 2013, n o 16 ad. <ref-law>).
Lors de la pesée des intérêts, le juge doit mettre en balance les dangers que représente l'auteur et la gravité de l'atteinte inhérente à la mesure. Il convient en particulier d'examiner si la personne soumise à la mesure menace de commettre des infractions et lesquelles, dans quelle mesure le risque est prononcé et quel poids est attaché au bien juridique menacé. Plus grave est l'infraction que la personne soumise à la mesure pourrait commettre en liberté, moins il est besoin que le risque soit important pour justifier une mesure privative de liberté (arrêt 6B_109/2013 du 19 juillet 2013 consid. 4.4.3).
L'atteinte au droit à la liberté doit être justifiée au regard des infractions graves dont on craint la commission et pour lesquelles la sécurité publique est mise en danger. Plus la durée de la mesure - et avec elle la privation de liberté de la personne concernée - est longue, plus strictes seront les exigences quant au respect du principe de proportionnalité. L'évaluation de la gravité des infractions visées à l'<ref-law> est soumise à adaptation en fonction de la durée croissante de la privation de liberté. Il est possible que les infractions dont on craint la commission en cas de libération de l'auteur soient toujours les mêmes que celles qui avaient conduit au pronostic de dangerosité à l'origine du prononcé de la mesure. La gravité de ces infractions mise en balance avec la durée croissante de la détention peut toutefois ne plus suffire pour justifier le maintien de la mesure. Le poids devenant plus important accordé au droit à la liberté se heurte toutefois à la limite lorsqu'il apparaît inadmissible, au vu de la nature et de l'importance du danger menaçant les biens juridiques des particuliers et de la collectivité, de libérer conditionnellement la personne soumise à la mesure, respectivement de lever la mesure (arrêt 6B_109/2013 du 19 juillet 2013 consid. 4.4.4).
2.8.2. Conformément aux conclusions de l'expertise, il est sérieusement à craindre que le recourant ne commette de nouvelles infractions portant gravement atteinte à l'intégrité physique, psychique ou sexuelle d'autrui. Les biens juridiques en cause sont en particulier l'intégrité physique et sexuelle. Au vu de la gravité des infractions, de la haute valeur des biens juridiques en cause et du risque important de récidive, il apparaît, en l'espèce, que l'atteinte au droit du recourant est encore largement proportionnée. La cour cantonale n'a pas violé le principe de proportionnalité et le grief du recourant est infondé.
3.
Le recourant fait grief à la cour cantonale d'avoir refusé d'ordonner une mesure thérapeutique institutionnelle en lieu et place de l'internement.
3.1. L'autorité compétente examine, d'office ou sur demande au moins une fois tous les deux ans et pour la première fois avant le début de l'internement, si les conditions d'un traitement thérapeutique institutionnel sont réunies et si une demande en ce sens doit par conséquent être faite auprès du juge compétent (<ref-law>).
Aux termes de l'<ref-law>, si, avant ou pendant l'exécution d'une peine privative de liberté ou d'un internement au sens de l'<ref-law>, le condamné réunit les conditions d'une mesure thérapeutique institutionnelle prévues aux art. 59 à 61 CP, le juge peut ordonner cette mesure ultérieurement.
3.2. Selon l'<ref-law>, un traitement thérapeutique institutionnel peut être ordonné en faveur d'une personne souffrant d'un grave trouble mental (a) si elle a commis un crime ou un délit en relation avec ce trouble et (b) s'il est à prévoir que cette mesure la détournera de nouvelles infractions en relation avec ce trouble.
3.3. En présence d'un trouble psychiatrique, l'internement constitue, conformément au principe de proportionnalité consacré par l'<ref-law>, une mesure subsidiaire par rapport à une mesure institutionnelle prévue par l'<ref-law>. En tant qu'ultima ratio, en raison de la gravité de l'atteinte à la liberté personnelle qu'il représente, l'internement n'entre ainsi pas en considération tant que la mesure institutionnelle apparaît utile. Ce n'est que lorsque cette dernière mesure semble dénuée de chances de succès que l'internement peut être maintenu, s'il est nécessaire. Cette démarche doit permettre d'éviter qu'un auteur soit déclaré a priori « incurable » et interné dans un établissement d'exécution des peines (<ref-ruling> consid. 3.2 et 3.3 p. 320 s.; 121 consid. 3.4.2 p. 130).
Le seul fait que l'intéressé soit désireux et apte à suivre un traitement institutionnel ne suffit toutefois pas à éviter l'internement ou son maintien. L'<ref-law> subordonne en effet le prononcé d'un traitement institutionnel à la condition qu'il soit à prévoir que cette mesure détournera l'intéressé de nouvelles infractions en relation avec son trouble. Tel est le cas lorsqu'au moment de la décision, il est suffisamment vraisemblable qu'un traitement institutionnel entraînera, dans les cinq ans de sa durée normale, une réduction nette du risque que l'intéressé commette, en raison de son trouble mental, un crime prévu à l'<ref-law>. La possibilité vague d'une diminution du risque ou l'espoir d'une diminution seulement minimale de ce risque ne sont en revanche pas suffisants (cf. <ref-ruling> consid. 3.4.1 p. 321 également arrêt 6B_92/2010 du 30 mars 2010 consid. 1.2).
L'exigence d'un tel pronostic ne signifie pas qu'un condamné souffrant de trouble mental ne pourra pas recevoir l'assistance nécessaire, mais seulement que la mesure préconisée par l'<ref-law> n'est pas adéquate ( QUELOZ/MUNYANKINDI, Commentaire romand, Code pénal I, 2009, n° 15 ad <ref-law>; GÜNTER STRATENWERTH, Schweizerisches Strafrecht, Allgemeiner Teil II, 2 e éd. 2006, n° 16 § 9), tout au moins dans l'état des choses au moment où la décision est rendue.
3.4. L'autorité compétente examine si les conditions d'un traitement thérapeutique institutionnel, remplaçant l'internement prononcé, sont réunies en se fondant sur un rapport de la direction de l'établissement, une expertise indépendante au sens de l'<ref-law> ainsi que l'audition d'une commission au sens de l'<ref-law> et de l'auteur (<ref-law>). L'expertise doit se déterminer sur la nécessité et les chances de succès d'un traitement, la vraisemblance que l'auteur commette d'autres infractions, la nature de celle-ci et les possibilités de faire exécuter la mesure (<ref-law>).
3.5. Le recourant souffre d'un grave trouble mental en lien avec le viol aggravé pour lequel il a été condamné en 1998. Reste donc à déterminer s'il était suffisamment vraisemblable, au moment où la décision attaquée a été rendue, qu'un traitement institutionnel entraînerait, dans les cinq ans de sa durée normale, une réduction nette du risque que l'intéressé commette de nouvelles infractions en lien avec ce trouble.
3.6. En résumé, la cour cantonale a retenu que les différentes tentatives de traitements avaient échoué en raison de l'hostilité persistante du recourant à toute forme de traitement. Il tentait ainsi de rejeter, encore une fois sur un tiers - l'Etat - son incapacité à se remettre en question et ses propres défaillances. Certes, il avait suivi des consultations psychiatriques, mais sans jamais qu'il en résulte le moindre profit significatif. Les possibilités de traitement étaient actuellement quasi inexistantes, la récente plainte pénale déposée par le recourant à l'encontre de ses derniers thérapeutes dénotant son absence de réceptivité à ce sujet. Même une simple administration statique et conservatoire de soins était impossible en raison de la rigidité du recourant. Espérer un « impact thérapeutique dynamique » était donc bel et bien une vue de l'esprit.
3.7. Quant à l'expert, il a relevé que le recourant avait bénéficié, à plusieurs reprises, d'une prise en charge psychiatrique. Toutefois, le même schéma se répétait à chaque fois en ce sens que le recourant semblait au départ s'inscrire dans une démarche thérapeutique, livrant des données sur sa vie personnelle, avant de glisser vers des revendications pour « rétablir la vérité », le recourant se sentant victime du système judiciaire. Il n'était ainsi pas possible de travailler sur la problématique de la violence et de la sexualité (cf. rapport d'expertise p. 33 à 38). L'expert a ainsi constaté que les traitements entrepris depuis 2008, date de la précédente expertise, n'avaient pas engendré d'évolution de l'état de santé du recourant, 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. S'agissant du déni, l'expert a indiqué que ce n'était pas ce seul élément qui était à l'origine de la stagnation du recourant, mais sa personnalité dans son ensemble. 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.
Lors de son audition, l'expert a indiqué qu'il existait des doutes sérieux quant à la possibilité d'évolution thérapeutique du recourant. Dans un cas comme celui-ci, où le traitement avait démontré ses limites et qu'il ne pouvait pas garantir une baisse du risque de récidive, l'expert devait se prononcer en faveur d'un internement.
3.8. En substance, le recourant soutient qu'il ne serait pas fermé à toute prise en charge psychiatrique et qu'il serait accessible à un traitement.
Il soutient qu'il serait faux de dire qu'il nie tout problème d'ordre psychique dès lors qu'il aurait accepté à plusieurs reprises de suivre une prise en charge thérapeutique. Ce faisant, le recourant ne fait qu'opposer sa propre appréciation à celle de l'expert et de l'autorité cantonale sans démontrer en quoi cette dernière serait arbitraire, en particulier au regard de ses déclarations à l'expert. En effet, lors de son entretien avec ce dernier, le recourant a répondu, à la question de savoir s'il estime souffrir de problèmes psychiatriques « que non, qu'il n'a pas quelque chose qui puise se remarquer, qu'il est plutôt une personne calme, posée, qui essaie de trouver des solutions plutôt que d'affronter les gens de manière agressive » (rapport d'expertise, p. 15). Au demeurant, le fait qu'il ait accepté de se rendre à des rendez-vous réguliers avec les psychiatres ou psychologues ne démontre pas encore qu'il ait pris conscience de ses graves problèmes psychiatriques, encore moins de la nature de ceux-ci. A cet égard, on relèvera que les différents intervenants ont tous constaté que le recourant glissait rapidement vers des revendications, ce qui tend bien à démontrer qu'il n'a pas compris les motifs et les buts d'une psychothérapie qu'il utilise plutôt pour, une nouvelle fois, remettre en cause les procédures judiciaires.
Le recourant conteste l'analyse de l'expert au sujet de son déni. A cet égard, il ne fait qu'opposer sa propre appréciation à celle de l'expert dans une démarche purement appellatoire, partant irrecevable. Le recourant soutient que l'expert aurait retenu de manière contradictoire que le déni n'avait pas d'influence directe sur la dangerosité tout en retenant que cet élément pouvait être rattaché à certains items, ce qui pousserait sensiblement l'évaluation de la dangerosité vers le haut. Ce faisant, le recourant procède d'une lecture biaisée du rapport. En effet, l'expert a indiqué « qu'il n'y a pas de correspondance directe entre la présence d'un déni et une augmentation de la dangerosité. L'évaluation de la dangerosité de l'expertisé se fonde sur de nombreuses variables, tant criminologiques que psychiatriques. Le déni, en soi, peut être rattaché à certains items (notamment dans la capacité d'assumer les faits et conséquences des actes) sur certaines échelles d'évaluation de la dangerosité, ce qui peut donc, pour certains items, pousser sensiblement l'évaluation de la dangerosité vers le haut. Toutefois, les outils d'évaluation du risque de passage à l'acte de nature violente et/ou sexuelle prennent en compte bien d'autres variables, et la question semble donc être ainsi mal posée » (rapport d'expertise p. 28). On comprend donc clairement qu'il n'existe pas de correspondance directeentre déni et dangerosité mais que c'est l'un des éléments qui est pris en compte, parmi d'autres, dans les échelles d'évaluation. L'expert ne s'est en outre pas fondé uniquement sur le résultat de ces évaluations mais également sur ses observations cliniques. C'est donc en ce sens que le déni peut avoir une certaine influence, celle-ci étant toutefois pondérée par les nombreux autres critères dont l'expert a tenu compte dans son évaluation de la dangerosité. Il n'y a donc aucune contradiction dans le raisonnement de l'expert. Pour le surplus, pour autant que l'on comprenne, le recourant semble soutenir que son déni n'empêcherait pas qu'il puisse bénéficier d'un traitement au sens de l'<ref-law>. S'il ressort effectivement de l'expertise que le déni n'empêche, en théorie, pas la prise en charge thérapeutique, l'expert a souligné que ce n'était pas le seul déni qui était à l'origine de la stagnation du recourant, mais sa personnalité dans son ensemble en particulier la composante paranoïaque marquée et les aspects pervers-narcissiques (cf. rapport d'expertise p. 27 s.). Au vu des développements figurant dans l'expertise, il n'était pas manifestement insoutenable de conclure qu'un éventuel traitement se rapprochait davantage d'une vue de l'esprit que d'une réalité.
Le recourant prétend que, lors de son prononcé sous l'ancien droit, la mesure d'internement avait pour objectif son traitement médical. Outre que l'application de l'ancien <ref-law> ne faisait pas dépendre l'internement d'une perspective de traitement médical (cf. <ref-ruling>), le recourant perd de vue que cette mesure a été transformée en internement au sens de l'<ref-law> par jugement du TAPEM du 5 décembre 2008, définitif et exécutoire, sur lequel il n'est pas fondé à revenir dans la présente cause. Dans la mesure où le recourant se réfère à un arrêt de la Cour européenne des droits de l'homme sans autre développement, son grief, insuffisamment motivé au regard des exigences accrues de l'<ref-law>, est irrecevable. Le recourant s'interroge en outre sur la disparition des perspectives de traitement de ses troubles mentaux dès lors que celles-ci auraient été présentes il y a quelques années. A cet égard, il peut être renvoyé aux conclusions de l'expert qui indique que les échecs répétés des tentatives de prise en charge et le temps écoulé conduisent à un pronostic de plus en plus défavorable quant aux chances de succès d'un traitement, celui-ci tendant à devenir une vue de l'esprit plutôt qu'une réalité.
En définitive, le recourant ne démontre pas qu'il était arbitraire de se rallier, comme l'a fait la cour cantonale, aux conclusions de l'expertise s'agissant des chances de succès d'un éventuel traitement.
3.9. Au vu du rapport d'expertise, en particulier des sérieux doutes éprouvés quant à la possibilité d'évolution thérapeutique du recourant, de l'échec des divers traitements entrepris et de leur absence d'effet sur le risque de récidive, la cour cantonale pouvait considérer, sans violation du droit fédéral, qu'il n'était pas établi qu'un traitement institutionnel entraînerait une réduction nette du risque que le recourant commette à nouveau des infractions. Le seul espoir ou l'envie du recourant de suivre un traitement n'est pas suffisant, étant ici rappelé que le pronostic exigé par l'<ref-law>, auquel se réfère l'<ref-law>, ne peut être admis au seul bénéfice du doute. C'est à bon droit que la cour cantonale a estimé que les conditions de l'<ref-law> n'étaient pas remplies.
3.10. Dans la mesure où le recourant se plaint de l'absence de traitement mis à sa disposition, se fondant sur des considérations d'ordre général sur la prise en charge des détenus internés, on peut douter que sa critique constitue un grief recevable. Quoi qu'il en soit, l'<ref-law> prévoit que l'auteur est soumis, si besoin est, à une prise en charge psychiatrique. Dès lors que le recourant est placé sous le régime de l'internement, il peut bénéficier d'un traitement psychiatrique. Le recourant a lui-même mis fin à sa dernière prise en charge sous le prétexte qu'il n'avait pas apprécié que ses thérapeutes rendent un rapport à son sujet à la demande de l'autorité. Il ne prétend, ni ne démontre qu'il ne pourrait pas reprendre un suivi thérapeutique, qui n'a été rendu impossible qu'en raison de son comportement.
4.
Le recours doit être rejeté dans la mesure où il est recevable. Les conclusions du recours n'étaient pas d'emblée dénuées de chances de succès et la situation économique du recourant justifie l'octroi de l'assistance judiciaire (<ref-law>). La complexité de la cause et les intérêts en jeu permettent qu'un avocat d'office lui soit désigné et indemnisé par la caisse du tribunal (<ref-law>). Il n'y a pas lieu de prélever des frais (art. 66 al. 1 et 4 LTF).

Par ces motifs, le Tribunal fédéral prononce:
1.
Le recours est rejeté dans la mesure où il est recevable.
2.
La demande d'assistance judiciaire du recourant est admise et Me Baptiste Viredaz, avocat à Lausanne, lui est désigné comme conseil d'office.
3.
Il n'est pas perçu de frais judiciaires.
4.
La caisse du Tribunal fédéral versera une indemnité de 2000 fr. à Me Baptiste Viredaz, à titre d'honoraires.
5.
Le présent arrêt est communiqué aux parties et à la Chambre pénale de recours de la Cour de justice de la République et canton de Genève.
Lausanne, le 12 décembre 2013
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président: Mathys
La Greffière: Livet