Faits: A. Par jugement du 23 juillet 2012, le Tribunal correctionnel du canton de Genève a condamné X._ pour infraction à la LEtr à une peine de 60 jours-amende à 30 fr. le jour avec sursis pendant trois ans, sous déduction de la détention préventive subie. Il l'a acquitté des chefs de tentative de meurtre et de contrainte sexuelle avec cruauté, a renoncé à révoquer le sursis accordé le 31 août 2011 et a débouté A._ de ses conclusions civiles. B. Sur appels de cette dernière et du Ministère public, la Chambre pénale d'appel et de révision de la Cour de justice du canton de Genève a, par arrêt du 20 décembre 2012, annulé le jugement du 23 juillet 2012, dans la mesure où il acquitte X._ de la prévention de contrainte sexuelle avec cruauté et prononce la peine susmentionnée. Elle a condamné X._ pour contrainte sexuelle avec cruauté (art. 189 ch. 1 et 3 CP) et séjour illégal en Suisse (art. 115 al. 1 let. b LEtr) à une peine de quatre ans et quatre mois, peine complémentaire à celle prononcée le 18 septembre 2012. X._ a de plus été astreint à supporter les frais de procédure de première instance et d'appel et à verser à A._ 20'000 fr. avec intérêt à 5% l'an dès le 14 octobre 2011 à titre d'indemnité pour tort moral et 30'494 fr. à titre d'indemnité de procédure. Le jugement du 23 juillet 2012 a été confirmé pour le surplus. En bref, la cour cantonale, se fondant sur les déclarations de A._ et écartant celles de X._, a retenu que ce dernier avait, le 14 octobre 2011, étranglé A._ afin d'obtenir d'elle une fellation et lui avait causé diverses lésions lors de cette agression. Il s'était ainsi rendu coupable de contrainte sexuelle avec cruauté au sens de l'art. 189 ch. 1 et 3 CP. La cour cantonale a en revanche considéré que l'intention de X._ de tuer n'était pas établie de sorte qu'il devait être acquitté du chef de tentative de meurtre. C. X._ forme un recours en matière pénale devant le Tribunal fédéral. Il conclut à l'annulation de l'arrêt cantonal, à son acquittement du chef de contrainte sexuelle avec cruauté, au rejet des prétentions de A._, à l'allocation en sa faveur de 20'000 fr. à titre de réparation du dommage économique enduré et de 50'000 fr. pour le tort moral subi. Subsidiairement, il requiert l'annulation de l'arrêt cantonal, le renvoi de la cause à l'autorité précédente pour nouveau jugement et que réserve lui soit donnée de ses droits en indemnisation de son dommage économique et de son tort moral. Il sollicite le bénéfice de l'assistance judiciaire. Aucun échange d'écriture n'a été ordonné.