Faits :
A.
A.a. X._, ressortissant serbe né en 1978, est entré en Suisse pour la première fois en date du 1er septembre 1990 et a été mis au bénéfice d'une autorisation de séjour par regroupement familial pour vivre auprès de ses parents. Suite à la séparation de ces derniers, l'intéressé est retourné vivre en Serbie avec son père le 30 juin 1995, alors que sa mère restait en Suisse. La mère de l'intéressé a présenté, en 2000 et 2004, deux demandes de regroupement familial en faveur de son fils, lesquelles ont été rejetées, ainsi que les recours y relatifs. Des demandes de visa pour séjour touristique ont également été refusées en 2006, 2008 et 2009.
En mai 2009, l'intéressé est revenu en Suisse muni d'un visa Schengen délivré par l'Ambassade de Slovénie à Belgrade. Durant son séjour, il a fait la connaissance de Y._, citoyenne italienne née en 1990 et titulaire d'une autorisation d'établissement. Ils se sont mariés en septembre 2010 à Martigny et l'intéressé a, de ce fait, été mis au bénéfice d'une autorisation de séjour par regroupement familial, afin de vivre auprès de son épouse. Cette autorisation a été prolongée jusqu'au 30 septembre 2017 (art. 105 al. 2 LTF). Les époux ont vécu des périodes de séparation dès le 1er mai 2013.
A.b. Dès mai 2013, soupçonnant l'existence d'un mariage de complaisance, le Service de la population et des migrations du canton du Valais (ci-après: le Service cantonal) a procédé à diverses mesures d'instruction. Le 3 octobre 2013, ledit service a informé l'intéressé qu'il avait l'intention de révoquer son autorisation de séjour dès lors qu'il ne formait plus ménage commun avec son épouse et que les conditions donnant droit à une autorisation de séjour après la dissolution de la famille n'étaient pas remplies.
Le 3 mars 2015, l'intéressé a introduit une requête de mesures protectrices de l'union conjugale. Son épouse étant à l'époque sans domicile ni séjour connus, ladite requête lui a été notifiée par le biais de la feuille officielle.
B.
Par décision du 20 février 2017, le Service cantonal a porté à la connaissance de l'intéressé qu'il soumettait son dossier à l'approbation du Secrétariat d'État aux migrations (ci-après : le SEM). Le 21 juillet 2017, le SEM, après avoir entendu l'intéressé, a rendu une décision de refus d'approbation à la prolongation de l'autorisation de séjour de ce dernier et prononcé son renvoi de Suisse.
Le couple, sans enfant, a divorcé le 4 octobre 2018.
Par arrêt du 17 décembre 2018, le Tribunal administratif fédéral a rejeté le recours formé par l'intéressé contre la décision précitée du SEM du 21 juillet 2017.
C.
Agissant par la voie du recours en matière de droit public, X._ demande au Tribunal fédéral, sous suite de frais et dépens, outre l'assistance judiciaire et l'effet suspensif, d'annuler l'arrêt précité du 17 décembre 2018 et d'ordonner au Service cantonal de lui octroyer une autorisation de séjour et au SEM de l'approuver.
L'effet suspensif sollicité par le recourant lui a été octroyé par ordonnance présidentielle du 24 janvier 2019. Après avoir été informé par le Tribunal fédéral que sa requête d'assistance judiciaire n'était pas suffisamment motivée, le recourant s'est acquitté de l'avance de frais dans le délai fixé, en précisant que le paiement avait été effectué par une tierce personne. Le recourant a par la suite complété sa requête d'assistance judiciaire.
Le Tribunal administratif fédéral a renoncé à prendre position sur le recours. Le SEM a conclu au rejet du recours. Le recourant a répliqué.
Considérant en droit :
1.
1.1. D'après l'art. 83 let. c ch. 2 LTF, le recours en matière de droit public est irrecevable contre les décisions en matière de droit des étrangers qui concernent une autorisation à laquelle ni le droit fédéral ni le droit international ne donnent droit. Selon la jurisprudence, il suffit qu'il existe un droit potentiel à l'autorisation, étayé par une motivation soutenable, pour que cette clause d'exclusion ne s'applique pas et, partant, que la voie du recours en matière de droit public soit ouverte. La question de savoir si les conditions d'un tel droit sont effectivement réunies relève du fond (ATF 139 I 330 consid. 1.1 p. 332 et les références; arrêt 2C_14/2014 du 27 août 2014 consid. 1, non publié in ATF 140 II 345).
En l'occurrence, le recourant se prévaut notamment de l'ancien art. 50 LEtr (RO 2007 5437; LEI depuis le 1er janvier 2019 [RS 142.20]), selon lequel, après dissolution de la famille, le droit du conjoint à l'octroi d'une autorisation de séjour et à la prolongation de sa durée de validité subsiste dans certains cas et de l'art. 8 CEDH (RS 0.101), notamment sous l'angle de la protection de la vie privée. Dès lors qu'il n'est pas d'emblée exclu que les conditions de ces dispositions soient remplies, il convient d'admettre que le recours échappe à la clause d'irrecevabilité de l'art. 83 let. c ch. 2 LTF. La voie du recours en matière de droit public est donc ouverte.
1.2. Au surplus, les autres conditions de recevabilité sont réunies (cf. art. 42, 82 let. a, 86 al. 1 let. a, 89 al. 1, 90 et 100 al. 1 LTF), si bien qu'il convient d'entrer en matière.
1.3. Le recourant a produit diverses pièces devant le Tribunal fédéral. Dans la mesure où elles ne concernent pas la requête d'assistance judiciaire et sont postérieures à l'arrêt attaqué, elles sont irrecevables, car nouvelles (art. 99 al. 1 LTF).
2.
Saisi d'un recours en matière de droit public, le Tribunal fédéral examine librement la violation du droit fédéral, y compris la violation des droits fondamentaux (cf. art. 95 let. a et 106 al. 1 LTF), sous réserve des exigences de motivation de l'art. 106 al. 2 LTF. Il n'examine les moyens de droit nouveaux que si les conséquences juridiques qui en sont déduites reposent entièrement sur les faits régulièrement soumis à l'appréciation de la juridiction précédente et constatés par elle dans la décision attaquée (art. 105 al. 1 LTF) ou complétés par le Tribunal fédéral en application de l'art. 105 al. 2 LTF (ATF 136 V 362 consid. 4.1 p. 366). Il s'ensuit que le grief de violation du droit à la protection de la vie privée, soulevé pour la première fois par le recourant devant le Tribunal fédéral pour obtenir une autorisation de séjour, est recevable.
3.
Le recourant se plaint d'arbitraire dans l'établissement des faits.
3.1. Selon l'art. 97 al. 1 LTF, le recours ne peut critiquer les constatations de fait que si les faits ont été établis de façon manifestement inexacte - notion qui correspond à celle d'arbitraire - ou en violation du droit au sens de l'art. 95 LTF et si la correction du vice est susceptible d'influer sur le sort de la cause (ATF 142 II 355 consid. 6 p. 358; 139 II 373 consid. 1.6 p. 377). La partie recourante doit expliquer de manière circonstanciée en quoi ces conditions seraient réalisées (cf. art. 106 al. 2 LTF).
L'appréciation des preuves et l'établissement des faits sont arbitraires lorsque le juge s'est manifestement mépris sur le sens et la portée d'un moyen de preuve, lorsqu'il a omis, sans raison sérieuse, de tenir compte d'un moyen important propre à modifier la décision attaquée, ou encore lorsqu'il a tiré des déductions insoutenables à partir des éléments recueillis (ATF 141 IV 369 consid. 6.3 p. 375; 140 III 264 consid. 2.3 p. 266; 136 III 552 consid. 4.2 p. 560).
3.2. Le recourant reproche tout d'abord à l'autorité précédente d'avoir retenu que son union conjugale avait duré moins de trois ans, ce qui porte en l'occurrence sur une question de fait (arrêts 2C_277/2019 du 26 mars 2019 consid. 5.1; 2C_976/2012 du 11 février 2013 consid. 3.2). Selon lui, si le Tribunal administratif fédéral avait estimé à raison que la communauté conjugale avait duré du 3 septembre 2010 au 1er mai 2013, soit deux ans et huit mois, il avait en revanche considéré à tort que la deuxième période de vie commune, commencée le 15 octobre 2013, avait cessé fin 2013, en se fondant sur la relation extra-conjugale entretenue par son ex-épouse à cette période. Il estime que le moment à prendre en compte était celui où celle-ci avait quitté le logement conjugal en avril-mai 2014. Le recourant fait en particulier valoir que l'autorité précédente n'a à tort pas tenu compte des troubles psychiques qui affectaient son ex-épouse et qui expliqueraient pourquoi celle-ci l'avait trompé. A cet égard, il mentionne qu'un certificat médical a confirmé l'existence de ces troubles et que son ex-épouse avait déclaré à plusieurs reprises souffrir de ceux-ci.
Le recourant ne précise toutefois pas de quel certificat il s'agit, ni ne spécifie les déclarations auxquelles il se réfère. Il n'allègue pas avoir valablement produit ce certificat, ni n'explique en quoi l'autorité précédente aurait fait preuve d'arbitraire dans l'appréciation des éléments qui se trouvaient au dossier. L'argumentation du recourant est ainsi sur ce point insuffisante au regard des exigences de motivation accrues de l'art. 106 al. 2 LTF. Par ailleurs, il est pleinement soutenable de considérer, comme l'a fait le Tribunal administratif fédéral, que l'on ne pouvait plus retenir l'existence d'une communauté conjugale effectivement vécue à partir du moment où l'ex-épouse du recourant a entrepris une nouvelle relation adultérine vers la fin de l'année 2013. Dans les présentes circonstances, le seul fait d'avoir partagé le même domicile jusqu'en avril-mai 2014 ne permet pas de conclure au maintien d'une union conjugale, ce d'autant plus qu'il ressort également de l'arrêt attaqué que l'ex-épouse du recourant aurait également vécu durant la période comprise entre janvier et juin 2014 alternativement chez sa mère et une amie, chez laquelle elle avait déposé une bonne partie de ses affaires personnelles. Enfin, l'arrêt attaqué ne retient aucun élément qui indiquerait que les époux avaient encore la volonté de former une union conjugale au début de l'année 2014.
Le grief d'arbitraire dans la constatation des faits est sur ce point infondé.
3.3. Le recourant reproche également à l'autorité précédente d'avoir retenu que son état de santé était bon. A cet égard, il indique avoir produit un certificat médical attestant qu'il souffrait d'une maladie grave, nécessitant un traitement quotidien et un suivi au long cours.
En l'occurrence, ces éléments ressortent du certificat du 23 novembre 2017 établi par une spécialiste en médecine interne et générale (dossier de l'autorité précédente; art. 105 al. 2 LTF). Ce document, certes laconique, ne permettait pas de retenir, sans autre motif, comme l'a fait l'autorité précédente, que le recourant était en bonne santé. Cela étant, cet élément est sans incidence sur l'issue du litige, ainsi qu'il sera vu ci-après (cf. infra consid. 4.2).
3.4. Le recourant estime également que l'autorité précédente a retenu à tort qu'il parlait couramment la langue serbe.
Sur ce point, le Tribunal administratif fédéral a retenu dans l'arrêt attaqué que le recourant avait passé la majorité de sa vie en Serbie, dont une partie de sa scolarité obligatoire et de sa vie d'adulte. Il a en outre relevé qu'il avait entièrement rempli un formulaire dans cette langue en mai 2010. Dans ces circonstances, et même si plusieurs années se sont écoulées depuis ce dernier acte, l'autorité précédente pouvait de façon soutenable retenir que le recourant n'avait pas pu perdre en seulement quelques années passées en Suisse la maîtrise ordinaire de sa langue maternelle.
3.5. Pour le surplus, l'argumentation du recourant est appellatoire et ne répond pas aux exigences de motivation de l'art. 106 al. 2 LTF. Elle ne peut partant pas être prise en compte (cf. supra consid. 2.1).
3.6. Sur le vu de ce qui précède, on ne peut reprocher à l'autorité précédente d'avoir établi les faits pertinents de manière arbitraire. Le moyen, pour autant qu'il soit recevable, est infondé. Dans la suite de son raisonnement, le Tribunal fédéral se fondera donc exclusivement sur les faits pertinents établis par le Tribunal administratif fédéral.
4.
Le litige porte sur le droit à l'obtention d'une autorisation de séjour après la dissolution de l'union conjugale.
4.1. Selon l'ancien art. 50 al. 1 let. a LEtr, après dissolution de la famille, le droit du conjoint à l'octroi d'une autorisation de séjour et à la prolongation de sa durée de validité en vertu des art. 42 et 43 LEtr subsiste si l'union conjugale a duré au moins trois ans et que l'intégration est réussie. Il s'agit de deux conditions cumulatives (ATF 140 II 289 consid. 3.5.3 p. 295; 136 II 113 consid. 3.3.3 p. 119). Selon la jurisprudence, la période minimale de trois ans de l'union conjugale commence à courir dès le début de la cohabitation effective des époux en Suisse et s'achève en principe au moment où ceux-ci cessent de faire ménage commun (ATF 138 II 229 consid. 2 p. 231; 136 II 113 consid. 3.2 p. 117). La limite des trois ans est absolue et s'applique même s'il ne manque que quelques jours pour atteindre la durée des trente-six mois exigés par l'art. 50 al. 1 let. a LEtr (cf. ATF 137 II 345 consid. 3.1.3 p. 347; 136 II 113 consid. 3.2 et 3.4 p. 116 s. et 120). Sous réserve d'un éventuel abus de droit, la jurisprudence admet que plusieurs périodes de vie commune en Suisse, même de courte durée et/ou qui sont interrompues par des temps de séparation prolongée, peuvent être additionnées en vue de satisfaire à la condition de la durée minimale de l'union conjugale, à condition que les époux soient véritablement et sérieusement déterminés à poursuivre leur communauté conjugale (ATF 140 II 345 consid. 4.5.2 p. 351).
4.2. D'emblée, il faut relever qu'il ressort des faits retenus dans l'arrêt attaqué que c'est suite au courrier du Service cantonal du 3 octobre 2013, qui annonçait au recourant qu'il entendait révoquer son autorisation de séjour du fait que celui-ci ne formait plus un ménage commun avec son épouse, que les époux ont chacun signé une déclaration en date du 15 octobre 2013 indiquant qu'ils reprenaient la vie commune à partir de cette même date (cf. également courrier des 15 et 16 octobre 2013; dos. SEM; art. 105 al. 2 LTF). Cette déclaration était donc à l'évidence liée à des considérations de droit des étrangers. Dans de telles circonstances, se pose la question d'un abus de droit à invoquer la seconde période de vie commune, soit celle qui aurait débuté le 15 octobre 2013, dans le calcul de la durée de l'union conjugale (cf. supra consid. 3.1). Cette question peut toutefois être laissée ouverte vu l'issue du recours.
4.3. Comme exposé ci-avant, le Tribunal administratif fédéral a estimé que le recourant avait formé avec son ex-épouse une communauté conjugale du 3 septembre 2010 au 1er mai 2013, soit durant deux ans et huit mois. Il a en outre retenu, sans arbitraire, que la seconde période de vie commune avait duré du 15 octobre 2013 à la fin de l'année 2013. Dès lors, même en prenant en compte cette seconde période, on arriverait à un total de deux ans et dix mois et demi, soit une durée d'union conjugale inférieure aux trois ans requis par l'art. 50 al. 1 let. a LEtr. L'autorité précédente a ainsi retenu à bon droit que la première condition prévue par cette disposition n'était pas remplie. Sur le vu de ce résultat, il n'est pas nécessaire d'examiner la seconde condition cumulative de l'intégration réussie. Le grief de violation de l'art. 50 al. 1 let. a LEtr doit être écarté.
5.
Le recourant reproche également à l'autorité précédente d'avoir nié l'existence de raisons personnelles majeures au sens de l'art. 50 al. 1 let. b et al. 2 LEtr, dont la teneur est identique à celle de l'art. 50 al. 1 let. b et al. 2 LEI.
5.1. L'art. 50 al. 1 let. b LEI dont se prévaut le recourant fonde un droit à la poursuite du séjour en Suisse de l'étranger dont l'union conjugale a duré moins de trois ans en cas de raisons personnelles majeures. Ces raisons sont notamment données lorsque la réintégration sociale du conjoint étranger dans le pays de provenance semble fortement compromise (cf. art. 50 al. 2 LEI). Comme il s'agit de cas de rigueur survenant à la suite de la dissolution de la famille, en relation avec l'autorisation de séjour découlant du mariage, les raisons qui ont conduit à sa dissolution revêtent par conséquent de l'importance. L'admission d'un cas de rigueur personnel survenant après la dissolution de la communauté conjugale suppose que, sur la base des circonstances d'espèce, les conséquences pour la vie privée et familiale de la personne étrangère liées à ses conditions de vie après la perte du droit de séjour découlant de la communauté conjugale (art. 42 al. 1 et 43 al. 1 LEI) soient d'une intensité considérable (ATF 138 II 393 consid. 3.1 p. 395; 137 II 345 consid. 3.2.3 p. 350).
5.2. En l'occurrence, il ressort de l'arrêt attaqué que le recourant est encore relativement jeune, sans charge de famille, qu'il a passé la majorité de sa vie en Serbie, soit son enfance, une partie de sa scolarité obligatoire et de sa vie d'adulte, qu'il en connaît la langue et qu'il y dispose d'un réseau familial non négligeable. Il ne sera donc pas dépourvu de ressources dans ce pays et rien ne permet de penser qu'il n'ait pas les facultés nécessaires de réadaptation. Le fait qu'il ait passé une partie de son adolescence en Suisse ne change rien à l'appréciation qui précède. Le recourant pourra en outre éventuellement bénéficier du soutien de ses proches restés en Suisse. De plus, il n'allègue pas qu'il ne pourra pas obtenir dans son pays d'origine les soins nécessaires au traitement de la maladie dont il prétend souffrir. Au surplus, il ressort également de l'arrêt attaqué que le recourant ne dispose pas d'une situation professionnelle stable en Suisse. Il n'y est pas particulièrement intégré sur le plan professionnel et social. Dès lors, même si son retour en Serbie ne sera pas exempt de difficultés, une réintégration ne paraît pas d'emblée insurmontable, étant précisé que le simple fait que l'étranger doive retrouver des conditions de vie qui sont usuelles dans son pays de provenance ne saurait suffire à maintenir son titre de séjour, même si ces conditions de vie sont moins avantageuses que celles dont cette personne bénéficie en Suisse (cf. arrêts 2C_972/2017 du 15 juin 2018 consid. 4.3; 2C_547/2017 du 12 décembre 2017 consid. 4.2 et les références citées). Par ailleurs, le recourant n'explique pas en quoi les circonstances de la dissolution de la communauté conjugale seraient propres à fonder un cas de rigueur au sens de l'art. 50 al. 1 let. b et al. 2 LEI. Les troubles psychiques de l'ex-épouse invoqués et le simple fait de ne pas être responsable de la rupture du lien conjugal ne sont à cet égard pas suffisants. En particulier, le fait d'avoir été trompé par sa femme ne s'apparente pas à une situation de violences conjugales (cf. arrêt 2C_917/2018 du 29 janvier 2019 consid. 6.2). Enfin, la relation de concubinage qu'il invoque n'est pas non plus de nature à fortement compromettre sa réintégration.
Sur le vu de l'ensemble de ces éléments, le Tribunal administratif fédéral n'a à juste titre reconnu aucun droit au renouvellement de l'autorisation de séjour fondé sur l'art. 50 al. 1 let. b et al. 2 LEI.
6.
Le recourant se prévaut de l'art. 8 CEDH, en faisant valoir la relation qu'il entretient depuis plusieurs mois avec sa concubine et avec laquelle il indique avoir le projet de fonder une famille. Il mentionne également la présence de ses parents en Suisse.
6.1. Selon la jurisprudence, un étranger peut, selon les circonstances, se prévaloir du droit au respect de sa vie privée et familiale au sens de l'art. 8 par. 1 CEDH, pour s'opposer à une éventuelle séparation de sa famille. Mais l'art. 8 CEDH vise en premier lieu la famille dite nucléaire, c'est-à-dire la communauté formée par les parents et leurs enfants mineurs (ATF 140 I 77 consid. 5.2 p. 80 s.; 137 I 113 consid. 6.1 p. 118). Le Tribunal fédéral admet aussi qu'un étranger puisse, exceptionnellement et à des conditions restrictives, déduire un droit à une autorisation de séjour de l'art. 8 par. 1 CEDH, s'il existe un rapport de dépendance particulier entre lui et un proche parent (hors famille nucléaire) au bénéfice d'un droit de présence assuré en Suisse, par exemple en raison d'une maladie ou d'un handicap (ATF 137 I 154 consid. 3.4.2 p. 159; 129 II 11 consid. 2 p. 13 s.).
Sous réserve de circonstances particulières, les concubins ne sont pas habilités à invoquer l'art. 8 CEDH. Ainsi, le Tribunal fédéral a précisé à de nombreuses reprises que l'étranger qui vit en union libre avec un ressortissant suisse ou une personne ayant le droit de s'établir en Suisse ne peut prétendre à une autorisation de séjour que s'il entretient depuis longtemps des relations étroites et effectivement vécues avec celui-ci ou s'il existe des indices concrets d'un mariage sérieusement voulu et imminent. D'une manière générale, il faut que les relations entre les concubins puissent, par leur nature et leur stabilité, être assimilées à une véritable union conjugale pour bénéficier de la protection de l'art. 8 par. 1 CEDH (arrêt 2C_401/2018 du 17 septembre 2018 consid. 6 et les références citées).
6.2. En l'espèce, le recourant, qui est majeur, divorcé et sans enfant, ne présente pas de lien de dépendance particulier par rapport à des membres de sa famille résidant en Suisse qui lui permettrait de se prévaloir du droit au respect de la vie familiale garanti par l'art. 8 par. 1 CEDH. Le recourant mentionne certes son père atteint d'un cancer de stade avancé, sans cependant fournir le moindre élément attestant de la dépendance de celui-ci avec lui. En outre, la maladie de son père ne ressort pas de l'arrêt attaqué. Le recourant n'allègue pas avoir valablement présenté cet élément devant l'autorité précédente ou que celle-ci aurait arbitrairement retenu les faits sur ce point. Enfin, il n'explique pas non plus en quoi les conditions d'une exception à l'interdiction des faits nouveaux seraient remplies (art. 99 al. 1 LTF; cf. arrêt 4A_229/2010 du 7 octobre 2010 consid. 1.3 non publié aux ATF 136 III 518). Ce fait ne peut ainsi pas être pris en compte.
En outre, la durée de la relation de concubinage de quelques mois invoquée par le recourant est relativement courte au regard des exigences jurisprudentielles en la matière et dépourvue d'enfant commun - même en gestation -, si bien qu'elle ne peut être assimilée à une véritable union conjugale (cf. ATF 144 I 266 consid. 2.5 p. 270; arrêts 6B_612/2018 du 22 août 2018 consid. 2.7; 2C_97/2010 du 4 novembre 2010 consid. 3.3). De plus, l'arrêt attaqué ne révèle aucun indice concret d'un mariage sérieusement voulu et imminent entre le recourant et sa concubine.
Dans ces circonstances, l'autorité précédente a à juste titre retenu que le recourant ne pouvait pas se prévaloir de l'art. 8 CEDH sous l'angle du droit au respect de la vie familiale.
7.
Le recourant invoque également l'art. 8 par. 1 CEDH sous l'angle de la protection de la vie privée.
7.1. Lorsque l'étranger réside légalement depuis plus de dix ans en Suisse, ce qui correspond en droit suisse au délai pour obtenir une autorisation d'établissement ou la naturalisation, il y a lieu de partir de l'idée que les liens sociaux qu'il a développés avec le pays dans lequel il réside sont suffisamment étroits pour que le refus de prolonger ou la révocation de l'autorisation de rester en Suisse doivent n'être prononcés que pour des motifs sérieux. Lorsque la durée de la résidence est inférieure à dix ans mais que l'étranger fait preuve d'une forte intégration en Suisse, le refus de prolonger ou la révocation de l'autorisation de rester en Suisse peut également porter atteinte au droit au respect de la vie privée (cf. ATF 144 I 266 consid. 3 p. 271 ss).
Les années passées en Suisse dans l'illégalité ou au bénéfice d'une simple tolérance - par exemple en raison de l'effet suspensif attaché à des procédures de recours - ne revêtent toutefois que peu de poids et ne sont par conséquent pas déterminantes (ATF 137 II 1 consid. 4.3 p. 8; 134 II 10 consid. 4.3 p. 23 s.).
7.2. En l'occurrence, le recourant a séjourné en Suisse un peu moins de cinq ans dans les années nonante. La durée de son second séjour dans ce pays, depuis mai 2009, était de presque dix ans au moment du prononcé de l'arrêt attaqué en décembre 2018. La question de savoir si la durée de dix ans retenue par la jurisprudence (cf. supra consid. 7.1) doit être réalisée de façon ininterrompue ou si plusieurs périodes de vie en Suisse peuvent être additionnées peut toutefois être laissée ouverte au vu des circonstances particulières du cas d'espèce. En effet, il convient de fortement relativiser la durée du second séjour du recourant en Suisse. Comme déjà mentionné, le Service cantonal avait envisagé de révoquer son autorisation de séjour dès octobre 2013 en raison de la dissolution de l'union conjugale et celle-ci a vraisemblablement été invoquée abusivement dès ce moment (cf. supra consid. 4.2). En outre, dès l'échéance de son autorisation de séjour, le 30 septembre 2017, le recourant n'a séjourné en Suisse qu'en raison de la procédure entreprise contre le refus d'approbation à une prolongation de séjour prononcé par le SEM le 21 juillet 2017. Dès lors, même en prenant en compte la première période passée en Suisse, la relativité du second séjour dès octobre 2013 empêche de considérer que le recourant a tissé des liens étroits avec la Suisse en se fondant sur la seule durée du temps passé dans ce pays. Le refus de prolonger l'autorisation de séjour ne nécessitait donc pas de motifs sérieux (cf. supra consid. 7.1). Le recourant, qui a au surplus vécu dans son pays d'origine de 1978 à 1990 et de 1995 à 2009, ne pouvant pas se prévaloir d'une intégration particulière en Suisse, le refus de prolonger ladite autorisation ne porte pas atteinte au respect de la vie privée garantie par l'art. 8 CEDH.
8.
Sur le vu de ce qui précède, le recours est rejeté. Le recours étant manifestement dépourvu de chances de succès, la demande d'assistance judiciaire est rejetée (art. 64 al. 1 LTF). Par conséquent, les frais judiciaires seront mis à la charge du recourant, mais ils seront fixés en tenant compte de sa situation financière (art. 65 al. 2 LTF). Il n'est pas alloué de dépens (art. 68 al. 1 et 3 LTF).
Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est rejeté.
2.
La demande d'assistance judiciaire est rejetée.
3.
Les frais judiciaires, arrêtés à 1'000 fr., sont mis à la charge du recourant.
4.
Le présent arrêt est communiqué au mandataire du recourant, au Secrétariat d'Etat aux migrations, au Tribunal administratif fédéral, Cour VI, et au Service de la population et des migrations du canton du Valais.
Lausanne, le 7 juin 2019
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président : Seiler
Le Greffier : de Chambrier