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 (art. 90 ch. 2 LCR), à 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'art. 64 CP, 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. 