Faits : A. Par jugement du 8 juillet 2019, le Tribunal correctionnel de l'arrondissement de l'Est vaudois a libéré A._ des chefs d'accusation de menaces et de contrainte, l'a condamné pour tentative de contrainte, contrainte sexuelle et viol à une peine privative de liberté de 5 ans, sous déduction de 57 jours de détention provisoire et 69 jours de détention pour des motifs de sûreté. Il a également ordonné l'expulsion de A._ du territoire suisse pour une durée de 12 ans et a dit que A._ était le débiteur de B._ d'un montant de 15'000 fr., avec intérêts à 5% l'an dès le 8 juillet 2018, à titre d'indemnité pour tort moral. B. Par jugement du 13 novembre 2019, la Cour d'appel pénale du Tribunal cantonal vaudois a rejeté l'appel formé par A._ à l'encontre du jugement précité, qu'elle a confirmé. Les faits retenus par la Cour d'appel pénale sont en substance les suivants. B.a. A._ est né en 1983 à C._, en Bosnie-Herzégovine, pays dont il est ressortissant. Après avoir suivi l'école primaire, il a effectué une formation de technicien en tourisme. II a ensuite travaillé dans le café de son père, tout en se lançant en parallèle, depuis 5 ans environ, dans le commerce de voitures d'occasion. Son revenu s'élève à un montant compris entre 1'000 et 1'500 euros par mois. Il vit chez sa mère à D._, en Bosnie-Herzégovine. Il a un enfant âgé de 9 ans, lequel vit en Allemagne avec sa mère et ancienne compagne, dont il a pris le nom de famille bien qu'ils n'étaient pas mariés. Il écrit régulièrement à son fils. Le casier judiciaire suisse de A._ comporte les inscriptions suivantes: - 19 août 2013, Ministère public du canton du Tessin, Bellinzone: faux dans les certificats; peine pécuniaire de 45 jours-amende à 100 fr., avec sursis pendant 3 ans, et amende de 1'100 francs; sursis révoqué le 26 février 2014; - 25 octobre 2013, Ministère public du canton de Soleure: vol; peine pécuniaire de 15 jours-amende à 30 fr., avec sursis pendant 2 ans, et amende de 200 francs; sursis révoqué le 26 février 2014; - 26 février 2014, Ministère public du canton du Valais, Office régional du Bas-Valais: vol; peine pécuniaire de 45 jours-amende à 100 fr., avec sursis pendant 2 ans; sursis révoqué le 30 septembre 2014; - 23 mars 2014, Ministère public du canton de Bâle-Ville: entrée illégale, séjour illégal, violation de domicile et vol d'importance mineure: peine pécuniaire de 60 jours-amende à 30 fr. et amende de 150 francs; - 21 août 2014, Ministère public régional de Berne-Mittelland: entrée illégale et séjour illégal; peine privative de liberté de 60 jours; - 30 septembre 2014, Ministère public de l'arrondissement de Lausanne: entrée illégale et séjour illégal; peine privative de liberté de 60 jours; - 20 avril 2017, Ministère public régional d'Altstätten: faux dans les certificats et conduite d'un véhicule automobile sans le permis de conduire requis; peine pécuniaire de 100 jours-amende à 30 francs; - 28 juillet 2017, Ministère public de l'arrondissement de l'Est vaudois: conduite d'un véhicule automobile sans le permis de conduire requis et contravention à l'OCR (Ordonnance sur les règles de la circulation routière du 13 novembre 1962; RS 741.11); peine pécuniaire de 50 jours-amende à 30 fr. et amende de 300 francs. Ce casier est établi au nom de E._, né en 1979, de nationalité croate. II est toutefois démontré que A._ a usé de cette identité et de faux papiers à ce nom afin de faciliter ses déplacements en Europe. D'ailleurs, l'extrait du casier mentionne l'identité réelle de l'intéressé, soit le nom de A._ et la date exacte de naissance en 1983, en tant qu'alias. En outre, y apparaît le nom de F._ sous la rubrique «nom de la mère» de E._. Or, il s'agit bien du nom de la mère de A._. Le prénommé a également un casier judiciaire en Allemagne, où il a fait l'objet des deux condamnations suivantes: - 13 décembre 2007, Tribunal de Rosenheim: recel, en concours avec entrée et séjour illégaux et séjour sans passeport; peine privative de liberté de 6 mois, avec sursis jusqu'au 27 décembre 2010; - 6 avril 2011, Tribunal de Miesbach: entrée et séjour illégaux après renvoi; peine pécuniaire de 130 jours-amende à 25 euros. A._ a enfin fait l'objet d'une condamnation en Italie, le 28 mars 2012, par le Tribunal de Milan, à une peine de réclusion de 8 mois et à une amende de 200 euros, avec sursis, pour complicité de tentative de vol. B.b. A._ a fait la connaissance de sa compatriote B._ au mois de juin 2018, en Suisse, par l'intermédiaire d'une connaissance commune. Ils sont allés manger ensemble à une reprise dans une pizzeria, à G._, à la fin du mois de juin 2018. B.b.a. Le 2 juillet 2018, A._ a pris contact par téléphone avec B._ pour lui demander de venir le chercher à la gare de H._ le lendemain. Celle-ci a accepté et s'est donc rendue à H._ le lendemain 3 juillet 2018 pour y prendre en charge A._ et le déposer, à sa demande, à 11h30 à I._, en Valais, où ce dernier devait prendre un véhicule. Ce même 3 juillet 2018, vers 14h00-15h00, A._ s'est présenté au domicile de B._, à J._, et lui a demandé de lui faire à manger, ce que cette dernière a accepté. Durant le repas, il lui a montré ses tatouages sur les bras, lui a déclaré être un criminel, être interdit d'entrée dans plusieurs pays (notamment en Allemagne et en Italie) et posséder plusieurs faux passeports. Il a également raconté à B._ qu'il avait abattu son beau-père en Bosnie, ce dernier ayant pris fait et cause pour sa fille dans le cadre de leur séparation. A un moment donné, lorsque B._ a voulu se lever de table, A._ l'a saisie par les poignets, l'a entraînée dans la chambre à coucher, puis l'a jetée sur le lit. B._ a tenté de se débattre, sans pouvoir empêcher A._ de se coucher sur elle et de mettre une de ses jambes entre les siennes. A._ a alors ouvert le pantalon de B._, puis lui a touché le sexe. Dès lors que la jeune femme pleurait, il lui a asséné une, voire deux gifles, avant de lui toucher à nouveau le sexe et d'introduire deux doigts dans son vagin. B._ s'est alors mise à crier. A._ s'est relevé sur ses genoux et s'est positionné devant elle, entre ses jambes qu'il a soulevées au-dessus de lui, tout retirant son pantalon et sa culotte. B._ a ensuite été pénétrée vaginalement, avant que A._ ne la retourne sur le ventre. Il l'a ensuite pénétrée analement, après l'avoir saisie au niveau des hanches. La jeune femme hurlant de douleur, A._ l'a saisie par la nuque et lui a enfoncé le visage sur le matelas, avant de lui dire que de toute manière, "les femmes adoraient ça" et que "c'était excitant". Postérieurement à l'acte sexuel, B._ demandé à A._ ce qui arriverait si elle venait à parler à quelqu'un de ce qui venait de se passer. Celui-ci a répondu qu'il la surveillait depuis le mois de février, qu'il savait tout sur elle, en particulier qu'elle avait des enfants, et que si elle venait à parler, il s'en prendrait à eux. Vers 16h30-17h00, A._ a quitté les lieux. Il est revenu sur place, pour y dormir, le même jour vers 20h00-20h30. B._, terrorisée par l'attitude intimidante adoptée et les menaces que A._ avait proférées précédemment, a accepté qu'il dorme sous son toit, ce que chacun a fait dans des pièces séparées. B.b.b. Le 6 juillet 2018 au matin, A._ est parti. Il est revenu au domicile de B._ vers 13h30. A un moment donné, alors qu'il sortait des toilettes, il a appelé B._, prétextant devoir lui montrer quelque chose. Lorsqu'elle s'est approchée de lui, elle a immédiatement remarqué que son pantalon était ouvert. A._ l'a alors agrippée par le bras et l'a poussée jusqu'à la chambre à coucher, avant de l'asseoir sur le lit. Il a ensuite baissé son pantalon, a attrapé B._ par les cheveux et a dirigé sa tête vers son sexe en érection. B._ a tourné la tête dans tous les sens pour manifester son refus. A._ l'a alors lâchée, puis l'a immédiatement poussée, avant de la coucher sur le lit. Il s'est ensuite posé à califourchon sur sa poitrine, et l'a à nouveau prise par les cheveux, avec une main. A l'aide de son autre main, il a dirigé son sexe vers la bouche de la jeune femme. Cette dernière refusant d'ouvrir la bouche, A._ lui a pincé le nez, afin de la contraindre à agir en ce sens, en vain. Il a également tenté de lui serrer la mâchoire inférieure, toujours sans succès. Alors que B._ tentait de se dégager, il l'a attrapée par les genoux, qu'il a soulevés, avant de lever la robe puis de baisser la culotte de sa victime. A._ l'a alors une nouvelle fois pénétrée vaginalement, avant d'éjaculer sur ses cuisses. B.b.c. B._ a revu une dernière fois A._ dans l'après-midi du 7 juillet 2018. Agacé d'apprendre qu'elle s'était visiblement confiée à une amie, A._ lui a répété qu'elle savait très bien ce qui allait lui arriver et qu'il était suffisamment malin pour ne pas se faire attraper par la police. Il a ensuite quitté les lieux. B.c. B._ a déposé plainte pénale et s'est constituée partie plaignante le 8 juillet 2018. L'examen effectué le même jour au Centre universitaire romand de médecine légale (ci-après: CURML) sur la personne de l'intéressée a permis de constater la présence des lésions traumatiques suivantes: - une ecchymose suprascapulaire droite; - une ecchymose de la face interne du coude droit; - une ecchymose de la face interne du tiers moyen de la cuisse droite; - une ecchymose de la face antéro-interne du genou droit; - une ecchymose du tiers moyen de la face antéro-interne de la jambe gauche; - une dermabrasion de la face externe du poignet gauche; - une dermabrasion de la face dorsale de la deuxième articulation métacarpo-phalangienne gauche. Les médecins du CURML n'ont pas constaté de lésions vaginales ni anales. Toutefois, selon leurs conclusions, l'absence de lésions ou de traces n'exclut pas des relations vaginales ou anales et ne donne pas d'information quant au fait que la relation sexuelle aurait été consentie ou non. Quant aux dermabrasions, elles pouvaient être contemporaines des faits, tandis que les ecchymoses pouvaient avoir été provoquées par un, voire des objets heurtant le corps ou contre lequel le corps s'est heurté, ou par une pression locale forte. Elles pouvaient être contemporaines des faits, étant précisé que B._ n'avait fourni aucun mécanisme lésionnel précis lors de son examen. C. A._ forme un recours en matière pénale au Tribunal fédéral contre le jugement de la Cour d'appel pénale du Tribunal cantonal vaudois du 13 novembre 2019. Il conclut, avec suite de frais et dépens, principalement, à l'annulation du jugement attaqué et au renvoi de la cause pour nouvelle instruction et nouvelle décision dans le sens des considérants. Subsidiairement, il conclut à la réforme du jugement entrepris en ce sens qu'il est en particulier libéré des chefs d'accusation de tentative de contrainte, contrainte sexuelle, viol, menaces et contrainte. Plus subsidiairement, il conclut à la réforme du jugement attaqué en ce sens qu'il est condamné à une peine privative de liberté de trois ans, sous déduction de la détention provisoire et de la détention pour des motifs de sûretés subies, et que son expulsion du territoire est ordonnée pour une durée de six ans. Il sollicite également le bénéfice de l'assistance judiciaire.