Faits:
A. Par jugement du 17 novembre 2008, le Tribunal correctionnel du district de Neuchâtel a condamné X._, pour contrainte sexuelle, viol, menaces, abus de confiance, utilisation frauduleuse d'un ordinateur et violation grave des règles de la circulation (<ref-law>), à trois ans de privation de liberté et a refusé de prononcer l'internement du condamné.
Sur recours du Ministère public, la Cour de cassation pénale du Tribunal cantonal neuchâtelois a, par arrêt du 4 février 2009, annulé le jugement en tant qu'il refusait de prononcer l'internement et renvoyé la cause aux premiers juges, afin qu'ils ordonnent cette mesure. Par arrêt du 1er septembre 2009, le Tribunal fédéral a déclaré irrecevable le recours déposé par X._.
B. Par jugement du 25 novembre 2009, le Tribunal correctionnel du district de Neuchâtel a, pour les motifs ressortant de l'arrêt de la Cour de cassation pénale du 4 février 2009, ordonné, en complément au jugement du 17 novembre 2008, l'internement de X._.
C. Invoquant une violation de l'<ref-law>, ce dernier dépose un recours en matière pénale au Tribunal fédéral. Il conclut, principalement, à la réforme du jugement précité en ce sens qu'il n'y a pas lieu de prononcer un internement à son encontre. Il sollicite, à titre subsidiaire, l'annulation de la décision attaquée et le renvoi de la cause pour complément d'enquête et nouveau jugement. Il requiert également l'assistance judiciaire.
Invités à se déterminer, les autorités et le Ministère public du canton de Neuchâtel n'ont pas déposé d'observations.

Considérant en droit:
1. Aux termes de l'<ref-law>, le recours est recevable contre les décisions prises par les autorités cantonales de dernière instance et par le Tribunal pénal fédéral.
En l'espèce, le recours est interjeté contre le jugement rendu, le 25 novembre 2009, par le Tribunal correctionnel, soit une autorité de première instance, qui a statué suite à un arrêt de renvoi de la Cour de cassation. Dans le cas particulier, ledit Tribunal doit toutefois être considéré comme une autorité cantonale de dernière instance au sens de la disposition précitée, dès lors que la Cour de cassation est elle-même liée par les motifs de son arrêt de renvoi (cf. art. 253 CPP/NE; ALAIN BAUER/PIERRE CORNU, Code de procédure pénale neuchâteloise annoté, Neuchâtel 2003 n° 2 ad art. 253 CPP/NE p. 528).
2. Le Tribunal fédéral statue sur la base des faits établis par l'autorité précédente (<ref-law>). Il ne peut s'en écarter que si ces faits ont été établis de façon manifestement inexacte ou en violation du droit au sens de l'<ref-law> (<ref-law>), et si la correction du vice est susceptible d'influer sur le sort de la cause (<ref-law>). Le recourant qui entend s'écarter des constatations de la juridiction cantonale doit exposer de manière circonstanciée en quoi les exceptions prévues par l'<ref-law> seraient réalisées (<ref-ruling> consid. 1.3 p. 152). Les faits nouveaux et les preuves nouvelles sont prohibés à moins de résulter de la décision de l'autorité précédente (<ref-law>).
2.1 Le recourant affirme, en se référant à divers éléments ou témoignages figurant au dossier, que la victime des infractions sexuelles était assez gravement perturbée, considérée comme fabulatrice et essentiellement préoccupée par le non-paiement du tarif convenu avec son client. Il allègue également avoir pris des mesures concrètes pour se maintenir dans le « droit chemin » suite à sa libération et décidé de se marier, de s'installer à St-Gall et de travailler pour le père de sa compagne.
Ce faisant, l'intéressé se prévaut de faits nouveaux, qui ne résultent pas de la décision de l'autorité précédente, de sorte que ces critiques sont irrecevables.
2.2 Le recourant prétend avoir pris conscience de ses erreurs passées.
Par cette argumentation, il s'écarte toutefois des constatations cantonales, sans invoquer l'arbitraire, ni expliquer, de manière circonstanciée, en quoi les faits retenus par les autorités cantonales seraient manifestement insoutenables. Ce grief, insuffisamment motivé, est donc irrecevable.
3. Invoquant une violation de l'<ref-law>, le recourant conteste que les conditions de l'internement soient réalisées.
3.1 Selon l'<ref-law>, une mesure doit être ordonnée si une peine seule ne peut écarter le danger que l'auteur commette d'autres infractions (let. a), si l'auteur a besoin d'un traitement ou que la sécurité publique l'exige (let. b) et si les conditions prévues aux art. 59 à 61, 63 ou 64 sont remplies (let. c). 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é (<ref-law>). Pour ordonner une des mesures prévues aux art. 59 à 61, 63 et 64 CP ou en cas de changement de sanction au sens de l'<ref-law>, le juge se fonde sur une expertise. Celle-ci se détermine sur la nécessité et les chances de succès d'un traitement, sur la vraisemblance que l'auteur commette d'autres infractions et sur la nature de celles-ci ainsi que sur les possibilités de faire exécuter la mesure (art. 56 al. 3 let. a à c CP).
3.1.1 L'internement fondé sur l'<ref-law> suppose d'abord que l'auteur ait commis l'une des infractions énumérées à l'alinéa 1 de cette disposition, soit un assassinat, un meurtre, une lésion corporelle grave, un viol, un brigandage, une prise d'otage, un incendie, une mise en danger de la vie d'autrui, ou une autre infraction passible d'une peine privative de liberté de cinq ans au moins et qu'il ait par là porté ou voulu porter gravement atteinte à l'intégrité physique, psychique ou sexuelle d'autrui.
Cette condition d'atteinte grave portée ou voulue à l'encontre de la victime vaut autant pour les infractions citées dans le catalogue que celles visées par la clause générale de l'<ref-law> (cf. MARIANNE HEER, Basler Kommentar, Strafrecht I, ad art. 64, n° 22 p. 1318). L'appréciation de l'atteinte doit être objective et tenir compte du principe de la proportionnalité. L'aspect subjectif du sentiment de la victime n'entre pas en considération (cf. NICOLAS QUELOZ/RAPHAËL BROSSARD, Commentaire romand, Code pénal I, ad art. 64 n° 18 p. 643; MARIANNE HEER, op cit, n° 24 p. 1318 s.; ).
3.1.2 Il faut en outre que l'une des conditions alternatives posées à l'<ref-law> soit réalisée, à savoir que, en raison des caractéristiques de la personnalité de l'auteur, des circonstances dans lesquelles il a commis l'infraction et de son vécu, il soit sérieusement à craindre qu'il ne commette d'autres infractions du même genre (let. a) ou que, en raison d'un grave trouble mental chronique ou récurrent en relation avec l'infraction, il soit sérieusement à craindre que l'auteur ne commette d'autres infractions du même genre et que la mesure prévue à l'<ref-law> - soit une mesure thérapeutique institutionnelle - apparaisse vouée à l'échec (let. b).
Ainsi, un trouble mental ne constitue plus forcément une condition préalable au prononcé de l'internement, de sorte qu'à certaines conditions déterminées, il est justifié d'ordonner l'internement d'un auteur mentalement sain en raison d'une infraction unique. Cette disposition permet l'internement de délinquants primaires dangereux qui ne présentent pas de trouble au sens de la psychiatrie, mais dont il est sérieusement à craindre, en raison des caractéristiques de leur personnalité, des circonstances dans lesquelles ils ont commis l'infraction et de leur vécu, qu'ils ne commettent d'autres infractions graves du même genre, si on les laisse en liberté. Il incombe au juge d'ordonner l'internement lorsque l'appréciation d'ensemble de ces éléments aboutit à un pronostic si défavorable que le risque d'une récidive apparaisse hautement vraisemblable (ATF 6B_486/2009 du 28 octobre 2009 consid. 6.6).
En revanche, en présence d'un trouble psychiatrique, l'internement fondé sur l'<ref-law> constitue, conformément au principe de proportionnalité, une mesure subsidiaire par rapport à une mesure institutionnelle au sens de l'<ref-law>. En tant qu'ultima ratio, en raison de la gravité de l'atteinte à la liberté personnelle qu'il représente (<ref-ruling> consid. 3.4.4 p. 131), l'internement n'entre pas en considération tant que la mesure institutionnelle apparaît utile. Il s'ensuit que pour les auteurs dangereux souffrant d'un grave trouble mental, il y a lieu d'examiner au préalable si une mesure institutionnelle au sens de l'<ref-law>, exécutée au besoin dans le cadre offrant une sécurité accrue prévu par l'<ref-law>, apparaît susceptible de les détourner de commettre de nouvelles infractions en rapport avec le trouble. Ce n'est ainsi que lorsqu'une mesure institutionnelle apparaît dénuée de chances de succès que l'internement peut être prononcé, 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.; <ref-ruling> consid. 3.4.2 p. 130).
3.1.3 Enfin, la mesure prononcée doit respecter le principe de la proportionnalité, c'est-à-dire que l'atteinte aux droits de la personnalité qui en résulte pour l'auteur ne doit pas être disproportionnée au regard de la vraisemblance qu'il commette de nouvelles infractions et de leur gravité (<ref-law>; ATF 6B_604/2007 du 9 janvier 2008 consid. 6.2).
3.2 En l'espèce, le recourant a notamment été condamné pour viol et contrainte sexuelle commis au préjudice de A._. La première infraction entre dans le catalogue des infractions citées par l'<ref-law> et la seconde dans la clause générale de cette disposition. L'intéressé a forcé sa victime à subir une relation sexuelle non protégée ainsi qu'une sodomie, alors qu'elle avait clairement manifesté son opposition. Certes, A._ avait consenti en partie à un rapport intime avec le recourant, puisqu'elle s'était rendue à l'hôtel en sachant qu'elle allait entretenir un rapport sexuel complet avec l'intéressé. Reste que ce dernier a largement outrepassé ce qui était convenu et a agi d'une manière condamnable. S'agissant de l'acte sexuel, la victime s'y est finalement opposée de peur de contracter une maladie et le recourant, sachant qu'il n'était pas affecté, l'a pénétrée sans protection. S'agissant de la sodomie, cet acte avait été clairement exclu et le recourant a passé outre.
Au regard de ces éléments, les autorités cantonales pouvaient, sans violation du droit fédéral, admettre que les infractions commises avaient porté une grave atteinte à la victime. Le fait que celle-ci se soit prostituée et que sa très forte réaction ait été probablement au-delà de ce qui était prévisible et trouvât ses racines dans des problèmes personnels ne modifie en rien cette appréciation, l'atteinte subie devant être appréciée objectivement et donc indépendamment des sentiments subjectifs de la plaignante (cf. supra consid. 3.1).
3.3 S'agissant des troubles constatés, il résulte de l'expertise du 14 février 2008 établie par le Docteur B._, que le recourant ne présente pas de signes de maladie mentale, mais un important trouble de la personnalité. L'expertisé frappe par la manière dont il adhère à une image grandiose de lui-même qu'il essaie d'imposer à l'interlocuteur en remaniant systématiquement la réalité sur un mode mythomaniaque. Il ment avec un aplomb considérable et persiste sans se laisser perturber même quand on le met en face de ses contradictions. Il y a chez lui une grande froideur affective. Ses réactions émotionnelles, qui peuvent être intenses, restent superficielles et versatiles et ses capacités d'empathie sont extrêmement faibles. L'expert a posé le diagnostic de personnalité dyssociale, qui se caractérise par une indifférence froide envers les sentiments d'autrui, une attitude irresponsable manifeste et permanente avec mépris des normes, des règles et des contraintes sociales, une incapacité à maintenir durablement des relations alors même qu'il n'existe pas de difficulté à en établir, une très faible tolérance à la frustration et un abaissement du seuil de décharge de l'agressivité, une grande difficulté à éprouver de la culpabilité ou à tirer un enseignement des expériences, notamment des sanctions, et enfin une tendance nette à blâmer autrui ou à fournir toutes sortes de justifications plus ou moins plausibles pour expliquer un comportement à l'origine d'un conflit entre le sujet et la société. L'expert a également constaté que la pathologie de l'empathie, que l'on ne retrouve pas, chez la majorité des délinquants dyssociaux, sous la forme et avec l'ampleur qu'elle prenait chez le recourant, semblait constituer le ressort fondamental du fonctionnement psychopathique de l'intéressé.
S'agissant du risque de récidive, le Docteur B._ a posé un pronostic défavorable. Selon cet expert, les psychopathes, tel que le recourant, sont caractérisés par un haut taux de récidive. Les mauvais traitements contre les partenaires sont habituels. Dans le cas particulier de l'expertisé, on semble assister à une sorte de clivage ou plutôt de compartimentation, la compagne du moment étant dévolue à une exploitation matérielle tandis que l'assouvissement de fantasmes sexuels teintés de violence est déplacé sur des professionnels. L'expert a ajouté que si la victime disait vrai - ce que les autorités ont retenu - on devait alors s'attendre à de nouveaux comportements similaires. En réponse aux questions qui lui ont été posées, le spécialiste a indiqué qu'il existait, du fait des caractéristiques de la personnalité de l'accusé, un haut risque de commission de nouvelles infractions, sous la forme de délits contre le patrimoine, principalement des escroqueries et des abus de confiance, et que de nouveaux abus de nature sexuelle, en particulier dans le cadre d'une relation tarifée, étaient aussi à craindre.
A la lecture de l'expertise, et plus particulièrement des réponses données, on constate que les risques de récidive envisagés par l'expert portent avant tout sur les infractions contre le patrimoine. Ce n'est en effet que très subsidiairement que le spécialiste se préoccupe de la récidive en matière d'infractions sexuelles, alors que seules celles-ci permettent ici l'application de l'<ref-law>. De plus, si les conclusions du Docteur B._ rejoignent celles de l'expertise effectuée le 22 mars 2007 par le Docteur C._, ce dernier ne s'est en revanche jamais prononcé sur le risque de récidive en matière d'infractions sexuelles, celles-ci s'étant déroulées en 2008, soit postérieurement au rapport rendu par ce médecin. Ainsi, les expertises n'apportent pas de réponses suffisamment claires et complètes sur le risque de récidive du recourant en matière d'infractions sexuelles et les éléments sont donc insuffisants pour trancher la question relative à la sécurité publique.
3.4 S'agissant des soins, le Docteur B._ a indiqué que même si le recourant était capable de trouver un couplet bien sonnant correspondant au stéréotype en vogue quant à ce qu'on pouvait attendre d'une psychothérapie, il n'y avait pas d'indication à celle-ci, puisqu'on ne disposait d'aucune méthode psychothérapeutique efficace pour modifier le comportement de sujets présentant un déficit de l'empathie comme celui de l'expertisé. En réponse aux questions posées, le psychiatre a constaté qu'il n'y avait ni traitement ambulatoire, ni traitement institutionnel susceptible de remédier au grave trouble du développement de la personnalité que présentait le recourant.
Dans son expertise du 22 mars 2007, le Docteur C._ a relevé que, lors de son séjour à Marsens, le recourant avait bénéficié d'une prise en charge intégrée, incluant une médication neuroleptique à visée anxiolytique et également dans le but de réduire l'impulsivité et améliorer la gestion du stress, une psychothérapie de soutien afin d'améliorer l'adaptation sociale et la gestion des contraintes et des frustrations et une prise en charge psychosociale en vue d'une réintégration socioprofessionnelle. Il a toutefois constaté que, malgré l'hospitalisation de neuf semaines, leur engagement, celui de sa famille et de sa tutrice afin de lui permettre de retrouver son équilibre personnel et de lui assurer une réadaptation socio-professionnelle, l'expertisé avait montré une tendance à multiplier les comportements de nature délictueuses (conduite de véhicule sans plaque et sans assurance, planification d'actes de brigandage, etc.) et des conduites à risque. L'expert en a déduit qu'une prise en charge thérapeutique serait insuffisante, voire inutile.
Selon le rapport du service de probation du 11 novembre 2008, le recourant a certes entrepris une prise en charge thérapeutique volontaire au sein de la prison préventive de La Chaux-de-Fonds depuis le 16 janvier 2008, à quinzaine jusqu'à sa libération provisoire en avril, les entretiens ayant ensuite repris de manière hebdomadaire au retour du prévenu en détention préventive dès le 16 juin 2008. La demande initiale était toutefois liée à un besoin de soutien suite à une rupture sentimentale, l'intéressé niant toute implication dans les faits reprochés. Lors de sa réincarcération suite à sa libération provisoire, le recourant a reconnu son côté manipulateur et a dit vouloir travailler dans la prise en charge. La thérapie est cependant difficile et le cadre doit sans cesse être rétabli au vu de la personnalité dyssociale et du comportement joueur et manipulateur du recourant. Le rapport ajoute que tout porte à croire que le but de l'intéressé reste la satisfaction à court terme de ses exigences mégalomaniaques sans tenir compte de l'éventuelle souffrance infligée pour ce faire à son entourage et que l'intéressé ne montre de plus aucune réelle remise en question de ses comportements délictueux.
Certes, à la lecture des rapports et avis précités, le recourant ne semble pas être accessible à un traitement, même s'il s'est soumis volontairement à une prise en charge thérapeutique. Reste qu'aucun psychiatre ne s'est jamais prononcé sur la question de l'internement, alors qu'en application de la loi (cf. art. 56 al. 3 let. c CP; supra consid. 3.1), l'expertise doit se prononcer sur les possibilités de faire exécuter une telle mesure.
3.5 Il s'ensuit que la cause doit être renvoyée à l'autorité cantonale afin qu'elle complète l'instruction sur ces différents points et qu'elle rende une nouvelle décision.
4. Le recours doit ainsi être admis dans la mesure où il est recevable. Il n'y a pas lieu de percevoir de frais judiciaires (<ref-law>). L'Etat de Neuchâtel versera en revanche une indemnité de dépens au recourant, qui obtient gain de cause avec l'assistance d'un avocat (<ref-law>). Vu l'issue du recours, la demande d'assistance judiciaire est sans objet.

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est admis dans la mesure où il est recevable, l'arrêt attaqué est annulé et la cause est renvoyée à l'autorité cantonale pour nouvelle décision.
2. Il n'est pas perçu de frais judiciaires.
3. Le canton de Neuchâtel versera en main du conseil du recourant la somme de 3000 fr. à titre de dépens.
4. La demande d'assistance judiciaire n'a plus d'objet.
5. Le présent arrêt est communiqué aux parties et au Tribunal correctionnel du district Neuchâtel.
Lausanne, le 22 mars 2010
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président: La Greffière:
Favre Bendani