Faits: A. A._, ressortissant tunisien né en 1976, est entré en Suisse le 1er décembre 2007 au bénéfice d'un visa de trois mois. Le 18 janvier 2008, il a épousé une ressortissante suisse et allemande, B._, née en 1939. Les époux s'étaient rencontrés en Tunisie plusieurs années auparavant. A._ a été mis au bénéfice d'une autorisation de séjour. Le 19 janvier 2009, B._ a déposé une requête en mesures protectrices de l'union conjugale auprès du Tribunal de première instance du canton de Genève. Elle a indiqué que leur vie de couple s'était rapidement détériorée et que la reprise d'une vie commune n'était plus possible. Par jugement du 7 mai 2009, le Tribunal de première instance a autorisé les intéressés à vivre séparés et a invité A._ à quitter le logement conjugal au plus tard au 31 juillet 2009. Le 21 septembre 2009, B._ a informé l'Office cantonal de la population du canton de Genève (ci-après: l'Office cantonal) que son époux ne vivait plus chez elle depuis le 8 mai 2009. B. Le 7 octobre 2009, l'Office cantonal a informé A._ de son intention de ne pas renouveler son autorisation de séjour. Par décision du 17 mars 2010, après avoir entendu l'intéressé, l'Office cantonal a agi en ce sens et a ordonné à A._ de quitter la Suisse avant le 17 juin 2010. L'Office cantonal a retenu que l'intéressé vivait séparé de son épouse et que, selon les déclarations de celle-ci, la reprise d'une vie commune était devenue insupportable. Il a ajouté que A._ n'était en Suisse que depuis un peu plus de deux ans, alors qu'il avait passé plus de trente ans dans son pays. L'intéressé n'exerçait, par ailleurs, aucune activité professionnelle depuis le 30 novembre 2009. Enfin, il retournait fréquemment en Tunisie, de sorte que son renvoi dans son pays d'origine n'était pas impossible. A._ a recouru contre ce prononcé auprès de la Commission cantonale de recours en matière administrative, devenue le Tribunal administratif de première instance du canton de Genève depuis le 1er janvier 2011 (ci-après: le TAPI), qui a rejeté le recours par décision du 1er novembre 2011. L'autorité cantonale a retenu que B._ n'avait jamais eu l'intention de former une véritable communauté conjugale avec A._; elle avait décidé de l'épouser afin de lui servir de tuteur. Il en résultait que le mariage contracté par les intéressés était un mariage de complaisance. Par ailleurs, rien ne s'opposait au renvoi de A._ en Tunisie, où il avait vécu pendant plus de trente ans. Enfin, le fait que B._ se serait opposée aux rites religieux de son époux ne pouvait être assimilé à de la violence conjugale. Le 9 décembre 2011, A._ a recouru auprès de la Chambre administrative de la Cour de justice du canton de Genève (ci-après: la Cour de justice) contre cette décision. Au cours de l'instruction, A._ a sollicité l'audition de cinq témoins. Ces personnes avaient connu A._ et B._ en Tunisie et pouvaient apporter des renseignements pertinents sur le couple qu'ils avaient formé. Le 27 mai 2013, le juge instructeur a reçu une copie d'une ordonnance pénale datée du 21 mai 2013 condamnant A._ à une peine pécuniaire de trente jours-amende à raison de 30 fr. par jour avec sursis pendant trois ans pour infraction à l'art. 118 al. 1 LEtr, au motif que l'intéressé avait trompé les autorités pour obtenir une autorisation de séjour en contractant un mariage de complaisance avec B._. Le 28 mai 2013, A._ a déclaré qu'il entendait faire opposition à l'ordonnance pénale et a requis la suspension de la procédure administrative jusqu'à droit jugé sur la procédure pénale. Le 14 juin 2013, A._ a produit le dispositif d'un jugement rendu le 12 septembre 2012 par le Tribunal de première instance prononçant le divorce des conjoints. Par arrêt du 30 juillet 2013, la Cour de justice a rejeté le recours de A._. Elle a retenu, en substance, que la durée de la vie commune des époux au sens de l'art. 50 al. 1 let. a LEtr était inférieure à trois ans et que les conditions de l'art. 50 al. 1 let. b LEtr n'étaient pas remplies. C. A._ forme un recours en matière de droit public et un recours constitutionnel subsidiaire contre l'arrêt de la Cour de justice. Outre l'effet suspensif et l'assistance judiciaire, il conclut principalement à l'annulation de l'arrêt de la Cour de justice du 30 juillet 2013 et à la prolongation par l'Office cantonal de son autorisation de séjour, subsidiairement au renvoi de la cause à la Cour de justice pour nouvelle décision dans le sens des considérants et à ce que celle-ci l'entende avant toute nouvelle décision et procède aux mesures probatoires nécessaires. Plus subsidiairement, A._ demande au Tribunal fédéral de renvoyer l'affaire à l'Office cantonal pour un nouvel examen au sens des considérants. L'Office cantonal renonce à déposer des observations. Se rapportant à la justice quant à la recevabilité du recours, la Cour de justice déclare persister dans les considérants et le dispositif de son arrêt. L'Office fédéral des migrations propose le rejet du recours. Le 25 septembre 2013, le Président de la IIe Cour de droit public a accordé l'effet suspensif au recours. Le Tribunal fédéral a renoncé provisoirement à demander une avance de frais et a informé l'intéressé qu'il sera statué ultérieurement sur sa demande d'assistance judiciaire.