Faits: A. A.X._, ressortissant péruvien né en 1980, est entré en Suisse le 19 juin 1998 au bénéfice d'une autorisation de séjour pour y effectuer ses études. Cette autorisation a été prolongée jusqu'au 30 juin 2004. Le 24 mai 2004, l'Office cantonal genevois de la population (ci-après: l'"OCP") a rejeté la demande de prolongation d'autorisation de séjour déposée par A.X._, motif pris que le but de son séjour sur notre territoire n'était pas atteint. Un délai au 23 août 2004 lui a été imparti pour quitter la Suisse. Le 21 juin 2004, A.X._ a recouru contre cette décision, et déposé simultanément une demande de réexamen. Celle-ci a été rejetée le 8 novembre 2004 par l'OCP qui a rendu à son encontre une nouvelle décision de refus d'autorisation et de renvoi. Le 13 juin 2005, l'Office fédéral des migrations, invité à se prononcer dans le cadre de la procédure de recours, a refusé d'exempter A.X._ des mesures de limitation en matière de séjour des étrangers. Par arrêt du 18 août 2009, le Tribunal administratif fédéral a rejeté le recours interjeté par l'intéressé contre cette décision. L'OCP a imparti A.X._ un délai au 10 janvier 2010 pour quitter la Suisse. B. Par arrêt du 27 février 2009, la Cour d'assises du canton de Genève a condamné A.X._ à une peine privative de liberté de trente-quatre mois pour actes d'ordre sexuel commis en avril 2006 sur une personne en état d'incapacité de discernement ou de résistance (cf. art. 191 du Code pénal suisse [CP]; RS 311.0). La peine a été prononcée sans sursis à raison de dix-sept mois, A.X._ étant mis, pour le surplus, au bénéfice du sursis partiel, avec un délai d'épreuve fixé à cinq ans. La Cour de cassation genevoise a, par arrêt du 14 septembre 2009, annulé l'arrêt du 27 février 2009 et renvoyé la cause à la Cour d'assises du canton de Genève. Celle-ci a, par arrêt du 7 juin 2010, arrêté la peine privative de liberté de A.X._ à vingt-neuf mois et quinze jours pour les faits incriminés, dont douze mois sans sursis, avec un délai d'épreuve de cinq ans. A.X._ s'est à nouveau pourvu en cassation. Par arrêt du 25 novembre 2010, la Cour de cassation genevoise a partiellement admis le pourvoi de A.X._ en tant qu'il portait sur la quotité de la peine ferme et la durée du délai d'épreuve. Le 21 mars 2011, le Tribunal correctionnel a rendu un jugement dans le sens des considérants de cet arrêt, fixant à dix mois la partie de la peine devant être exécutée par A.X._, avec un délai d'épreuve de trois ans. Par jugement du 7 juillet 2011, la Chambre pénale d'appel et de révision de la Cour de justice a rejeté l'appel formé par l'intéressé contre le jugement du 21 mars 2011. Le 12 septembre 2011, A.X._ a déposé un recours en matière pénale devant le Tribunal fédéral contre les arrêts du 14 septembre 2009 et du 25 novembre 2010 de la Cour de cassation et l'arrêt du 7 juillet 2011 de la Chambre pénale d'appel et de révision de la Cour de justice. En substance, il se plaignait d'une violation des art. 448 ss du Code de procédure pénale suisse (CPP; RS 312), d'un déni de justice formel et de la violation de son droit d'être entendu (cf. art. 29 al. 1 et 2 Cst.). Il invoquait aussi une motivation insuffisante dans la prise en compte d'une incapacité de résistance de la partie plaignante ainsi que la violation des art. 47 et 50 CP relatifs à la quotité de la peine, et, enfin, la violation de l'art. 29 al. 3 Cst. Au surplus, A.X._ a fait l'objet des condamnations pénales suivantes: - une peine pécuniaire de quinze jours-amende à CHF 30.-, avec sursis pendant trois ans, ainsi qu'une amende de CHF 100.-, pour conduite en état d'ébriété avec un taux d'alcool qualifié, prononcées par le Ministère public genevois par ordonnance du 2 juillet 2009, entrée en force. - une peine pécuniaire de trente jours-amende à CHF 50.-, sous déduction d'un jour-amende, pour conduite en état d'ébriété avec taux d'alcool qualifié, prononcée par le Ministère public genevois par ordonnance du 30 août 2011, entrée en force. Le sursis du 2 juillet 2009 a été révoqué. C. Le 6 avril 2010, A.X._ s'est marié avec B.X._, une ressortissante suisse et péruvienne. Invoquant le regroupement familial avec son épouse, A.X._ a déposé auprès de l'OCP, le 26 avril 2010, une requête tendant à l'octroi d'une autorisation de séjour. Le 11 novembre 2010, l'OCP a refusé de mettre A.X._ au bénéfice d'une telle autorisation. A.X._ et B.X._ ont recouru auprès du Tribunal administratif de première instance du canton de Genève contre cette décision. Par jugement du 12 avril 2011, le Tribunal de première instance a rejeté le recours des époux A.X._ B.X._, au motif que la condamnation de A.X._ à une peine privative de liberté supérieure à deux ans constituait un motif de révocation de l'autorisation de séjour, dès lors que la culpabilité de l'intéressé, aussi bien que la quotité de la peine, étaient déterminées. Le 1er juillet 2011, un recours contre ce jugement a été déposé par les époux A.X._ B.X._ devant la chambre administrative de la Cour de justice genevoise (ci-après: la "Cour de justice"). D. Par arrêt 6B_597/2011 du 10 avril 2012, le Tribunal fédéral a rejeté le recours formé par A.X._ contre les arrêts du 14 septembre 2009 et du 25 novembre 2010 de la Cour de cassation et l'arrêt du 7 juillet 2011 de la Chambre pénale d'appel et de révision de la Cour de justice. Le Tribunal de céans a en particulier jugé que la Cour de justice avait correctement fixé et motivé la peine infligée à A.X._, qui n'apparaissait pas sévère au point de constituer un abus du pouvoir d'appréciation. E. Par arrêt du 17 avril 2012, la Cour de justice a rejeté le recours déposé le 1er juillet 2011 par les époux A.X._ B.X._ contre le jugement du 12 avril 2011 du Tribunal de première instance. Elle a relevé qu'au jour de ce prononcé, "le Tribunal fédéral n'a[vait] pas encore rendu son arrêt dans la procédure pénale P/6488/2006" (cf. arrêt attaqué, n. 38 ad p. 8). Elle a toutefois jugé que la condamnation de A.X._ pour actes d'ordre sexuel commis sur une personne incapable de discernement ou de résistance pouvait être prise en compte comme motif de révocation propre à refuser l'octroi d'une autorisation de séjour en faveur de l'intéressé, quand bien même le recours correspondant en matière pénale était "encore pendant au Tribunal fédéral". La pesée des intérêts commandait par ailleurs le renvoi de Suisse de A.X._. F. Agissant par la voie du recours en matière de droit public, A.X._ demande au Tribunal fédéral, principalement, d'annuler l'arrêt du 17 avril 2012 de la Cour de justice et d'admettre sa demande d'autorisation de séjour pour regroupement familial; subsidiairement, de retourner le dossier à l'autorité cantonale pour nouvelle décision dans le sens des considérants. Il requiert, à titre préalable, que son recours soit doté de l'effet suspensif. Il se plaint, en substance, d'une violation de la présomption d'innocence, ainsi que d'une violation de l'art. 8 CEDH. S'en rapportant à justice quant à la recevabilité du recours, la Cour de justice persiste dans les considérants et le dispositif de son arrêt. L'OCP se réfère à l'arrêt de la Cour de justice et ne formule pas d'observation sur le recours. L'Office fédéral des migrations conclut au rejet de celui-ci. Par ordonnance présidentielle du 30 mai 2012, la requête d'effet suspensif a été admise. Par courrier séparé du 21 juin 2012, A.X._ et B.X._ ont demandé leur mise au bénéfice de l'assistance judiciaire. 