Faits:
A. Par jugement du 25 janvier 2010, le Tribunal du IIème arrondissement pour le district de Sion a reconnu X._ coupable de viols, tentative de viol et contraintes sexuelles. Il l'a condamné à une peine privative de liberté de cinq ans, sous déduction de la détention avant jugement, et l'a soumis à une mesure d'internement selon l'<ref-law>.
B. Statuant sur appel le 4 juillet 2011, la Cour pénale II du Tribunal cantonal valaisan a confirmé le jugement de première instance.
En résumé, elle a retenu les faits suivants :
Z._ a fait la connaissance de X._ lors de visites qu'elle rendait à un codétenu aux Établissements St-Jean du Landeron, où X._ était incarcéré depuis 2005. Dès décembre 2006, X._ a bénéficié de congés accompagnés. Z._ a fonctionné comme accompagnante le 18 avril 2007 pour la première fois. Alors qu'ils étaient chez elle, X._, qui avait bu, l'a empoignée par le poignet gauche et a voulu l'emmener de force dans la chambre à coucher en vue de pratiquer une relation sexuelle. Il a clairement indiqué sa volonté de faire l'amour avec Z._, qui a résisté en se tenant au cadre de la porte et en criant sa peur. La porte d'entrée était grande ouverte, de sorte que X._ n'a pas insisté et est parti avec la voiture de Z._.
Arrivé à Sion, X._ a demandé sa route à Y._, lui précisant qu'il venait d'avoir des problèmes avec sa copine. Y._ lui a proposé de venir chez elle. X._ a pleuré et a parlé avec Y._. Etant fatigué, il lui a dit qu'il ne pouvait pas conduire et l'a suppliée de lui prêter un coin de son lit. Vers 2 heures du matin, il a contraint Y._ à l'acte sexuel. Il a tiré le pantalon qu'elle retenait, se mettant à genoux sur elle, et lui a écarté les jambes. Il lui a asséné un « coup de boule » au front qui l'a « sonnée » et l'a pénétrée, puis sodomisée. Il l'a ensuite contrainte à faire des fellations. Y._ a eu très mal, elle pleurait et était complètement « nase ». Plus tard, ne parvenant pas à s'endormir, X._ est allé chercher un préservatif et a pénétré Y._ une nouvelle fois.
C. Contre l'arrêt cantonal, X._ dépose un recours en matière pénale devant le Tribunal fédéral. Il conclut à la réforme de l'arrêt attaqué en ce sens qu'il soit acquitté. Il dénonce une violation du fardeau de la preuve et se plaint d'avoir été condamné en l'absence de toute preuve de culpabilité. En outre, il sollicite l'assistance judiciaire.
Il n'a pas été ordonné d'échange d'écritures.

Considérant en droit:
1. Le recourant dénonce la violation de la présomption d'innocence.
1.1 La présomption d'innocence, garantie par l'art. 32 al. 1 Cst., porte sur la répartition du fardeau de la preuve dans le procès pénal, d'une part, et sur la constatation des faits et l'appréciation des preuves, d'autre part. La cour cantonale n'a pas renversé, en l'espèce, le fardeau de la preuve. En effet, elle n'a pas retenu que le recourant avait tenté de violer Z._ et avait violé Y._ au motif qu'il n'aurait pas prouvé son innocence, mais parce qu'elle en avait acquis la conviction au vu des déclarations des deux victimes. Dans la mesure où le recourant invoque la présomption d'innocence comme règle d'appréciation des preuves, ce grief se confond avec celui d'appréciation arbitraire des preuves (<ref-ruling> consid. 2a p. 87 s.; <ref-ruling> consid. 2 p. 33 ss).
Le grief d'arbitraire doit être invoqué et motivé de manière précise (<ref-law>). Le recourant 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. 6 p. 397).
1.2 En ce qui concerne Z._, le recourant fait valoir que la bonté et l'intérêt de la victime à son encontre était de nature à lui faire croire qu'elle n'était pas complètement opposée à entretenir une relation sexuelle. Il l'aurait simplement étreinte d'une manière un peu pressante, afin de lui ôter, non pas toute résistance, mais tout ultime remords ou hésitation. Il se serait arrêté de lui-même, sans aucun élément extérieur, lorsqu'elle aurait crié. Par cette argumentation, le recourant se borne à présenter sa propre version des faits, sans démontrer que la version des faits retenue par la cour cantonale sur la base des déclarations de la victime serait arbitraire. Insuffisamment motivés, les griefs du recourant sont irrecevables (<ref-law>).
1.3 En ce qui concerne Y._, le recourant soutient avoir entretenu des relations sexuelles normales et consenties avec sa victime. Il met en cause les déclarations de la victime, l'accusant d'avoir agi par ressentiment, lorsqu'elle s'était rendue compte dans les jours ayant suivi cette nuit qu'il lui avait menti sur sa situation. Il fait valoir qu'elle aurait donné des versions différentes des faits à deux médecins, qu'il n'était pas en mesure de se mettre à genoux sur sa victime en raison d'une opération qu'il aurait subie et que les voisins auraient dû entendre des cris. Il s'étonne enfin que la victime ait pris congé de lui en l'embrassant.
Par cette argumentation, le recourant se borne à présenter sa propre version des faits, sans démontrer en quoi les faits arrêtés par la cour cantonale sont arbitraires. La cour de céans ne voit pas en quoi les versions présentées aux deux médecins sont contradictoires. La victime a pu rencontrer son beau-frère en début de soirée et se faire violer par le recourant pendant la nuit, étant précisé que celui-ci a quitté sa précédente victime à 20h20. Bien que récemment opéré, le recourant pouvait marcher, de sorte que l'on ne voit pas pourquoi il n'aurait pas pu s'agenouiller. La victime ne prétend pas avoir hurlé ; le recourant lui a asséné un « coup de boule » au front, de sorte qu'elle a été « sonnée ». Enfin, lorsqu'il soutient que la victime l'a embrassé en le quittant, il allègue un fait qui n'est pas établi. Dans la mesure où ils sont recevables, les griefs soulevés par le recourant doivent donc être rejetés.
2. En relation avec la tentative de viol sur la personne de Z._, le recourant fait valoir que le fait de ceinturer une femme de manière maladroite ne peut être qualifié de tentative de viol, dans la mesure où aucun des deux protagonistes n'était dévêtu. On peut se demander si la motivation de ce grief répond aux exigences posées à l'<ref-law> ; cette question peut toutefois rester indécise, puisque ce grief est de toute façon infondé, pour les motifs suivants.
2.1 Il y a tentative lorsque l'auteur a réalisé tous les éléments subjectifs de l'infraction et manifesté sa décision de la commettre, alors que les éléments objectifs font, en tout ou en partie, défaut (<ref-ruling> consid. 7.2.1 ; <ref-ruling> consid. 3b). La délimitation entre les actes préparatoires, en principe non punissables (sous réserve de l'<ref-law>), et le commencement d'exécution, constitutif d'une tentative inachevée punissable, est délicate. D'après la jurisprudence, il y a commencement d'exécution dès que l'auteur accomplit un acte qui représente, dans son esprit, la démarche ultime et décisive vers la réalisation de l'infraction, celle après laquelle il n'y aura en principe plus de retour en arrière, sauf apparition ou découverte de circonstances extérieures compliquant trop ou rendant impossible la poursuite de l'entreprise (<ref-ruling> consid. 7.2.1). La distinction entre les actes préparatoires et ceux constitutifs d'un début d'exécution de l'infraction doit être opérée au moyen de critères avant tout objectifs. En particulier, le seuil à partir duquel il y a tentative ne doit pas précéder de trop longtemps la réalisation proprement dite de l'infraction (<ref-ruling> consid. 7.2.1 ; <ref-ruling> consid. 3). Le seuil de la tentative est en tout cas franchi si l'auteur réalise déjà l'un des éléments objectifs de l'infraction (<ref-ruling> consid. 7.2.1).
2.2 En l'espèce, il ressort des faits constatés, dont le recourant n'a pas démontré l'arbitraire et qui lient par conséquent la cour de céans (art. 105 al. 1 et 2 LTF), que le recourant a empoigné sa victime et a voulu l'emmener de force dans la chambre à coucher en vue de lui faire subir une relation sexuelle contre son gré. Par ce comportement, il a commencé à se montrer menaçant et a ainsi accompli les actes décisifs qui, selon le cours ordinaire des choses, devaient aboutir à la consommation du viol. Il a renoncé à violer sa victime, uniquement en raison de sa résistance et de ses cris. Il est à cet égard sans importance que les protagonistes n'aient pas été dévêtus. Au vu des faits constatés, la cour cantonale n'a donc pas violé le droit fédéral en retenant une tentative de viol.
3. Au vu de ce qui précède, le recours doit être rejeté dans la mesure où il est recevable. Comme ses conclusions étaient vouées à l'échec, l'assistance judiciaire ne peut être accordée (<ref-law>). Le recourant devra donc supporter les frais (<ref-law>), dont le montant sera toutefois fixé en tenant compte de sa situation financière.

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 est rejetée.
3. Les frais judiciaires, arrêtés à 1600 fr., sont mis à la charge du recourant.
4. Le présent arrêt est communiqué aux parties et au Tribunal cantonal du canton du Valais, Cour pénale II.
Lausanne, le 7 novembre 2011
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président: Mathys
La Greffière: Kistler Vianin