Faits: A. A.a. X._, ressortissant camerounais né en 1969, est arrivé en Suisse le 1 er décembre 2003. Il a déposé le même jour une demande d'asile auprès du Centre d'enregistrement de Vallorbe. Par décision du 8 juin 2004, l'Office fédéral des réfugiés (aujourd'hui: l'Office fédéral des migrations) a rejeté la demande d'asile de l'intéressé, a prononcé son renvoi de Suisse et lui a imparti un délai de départ au 3 août 2004. Par arrêt du 3 août 2004, la Commission de recours en matière d'asile (aujourd'hui: le Tribunal administratif fédéral) a déclaré irrecevable le recours déposé contre cette décision. Un nouveau délai de départ au 28 septembre 2004, prolongé au 5 janvier 2005, a été imparti à X._. L'intéressé n'a toutefois pas quitté la Suisse et a été signalé comme disparu dès le mois de juin 2005. A.b. A la fin du mois d'octobre 2008, X._ et Y._, une citoyenne suisse née en 1982, ont entrepris des démarches auprès de l'Office de l'état civil du Nord vaudois en vue de se marier. Le 5 novembre 2008, X._ s'est annoncé auprès du Bureau des étrangers de la Commune de Z._ et a sollicité une autorisation de séjour en vue de mariage. Le 13 juin 2009, X._ et Y._ se sont mariés. Aucun enfant n'est issu de leur union. X._ a en revanche quatre enfants nés de précédentes relations. Ces derniers, âgés respectivement de 19, 18, 14 et 12 ans, vivent au Cameroun avec leurs mères. Le 15 juillet 2009, X._ a été mis au bénéfice d'une autorisation de séjour par regroupement familial. Par demande du 1 er décembre 2010, Y._ a ouvert action en annulation de mariage. Elle a exposé que son mari n'avait jamais voulu fonder une communauté conjugale mais bien consolider sa situation tant administrative que financière à ses dépens. Elle a également reproché à son mari d'être encore marié à sa précédente épouse, l'accusant ainsi de bigamie. Sur ordre du Président du Tribunal civil de l'arrondissement de A._, X._ a quitté l'appartement conjugal le 7 décembre 2010. En mai 2012, la procédure en annulation de mariage a été transformée en procédure de divorce avec accord complet. Le divorce a été prononcé le 22 février 2013. A.c. Depuis 2009, X._ a occupé divers emplois temporaires dans les domaines de la construction et de la restauration. Entre décembre 2010 et septembre 2011, il a obtenu des prestations de l'aide sociale en complément de ses revenus. Depuis le 1 er septembre 2012, il est au bénéfice d'un contrat de travail de durée indéterminée auprès de la société B._. Travaillant à 50% comme aide-cuisine, il réalise un salaire mensuel net de 1'500 francs. Parallèlement à cette activité, il exerce des missions temporaires pour la société C._ qui lui procurent un revenu mensuel net variant entre 1'000 et 1'500 francs. Le 7 juin 2013, il a été engagé par la Municipalité de A._ comme ouvrier d'entretien pour une mission d'un mois du 15 juillet au 18 août 2013. En octobre 2012, X._ avait des poursuites pour un montant total de 6'018 fr. 70. B. Par décision du 19 novembre 2012, le Service de la population du canton de Vaud (ci-après: le Service cantonal) a refusé de prolonger l'autorisation de séjour de X._ et a prononcé son renvoi de Suisse. Le recours formé contre ce prononcé auprès de la Cour de droit administratif et public du Tribunal cantonal du canton de Vaud (ci-après: le Tribunal cantonal) a été rejeté le 3 juillet 2013. C. X._ forme un recours en matière de droit public contre le jugement du Tribunal cantonal. Outre l'effet suspensif et l'assistance judiciaire, il conclut au renouvellement de son autorisation de séjour, subsidiairement au renvoi de la cause au Tribunal cantonal pour nouvelle décision dans le sens des considérants, le tout sous suite de frais et dépens. Le 11 septembre 2013, le Président de la IIe Cour de droit public a accordé l'effet suspensif au recours. Il n'a pas été requis d'échange d'écritures.