Faits :
A.
A._, ressortissant macédonien né en 1981, est arrivé en Suisse le 19 décembre 2001 pour y déposer une demande d'asile, rejetée le 7 février 2003. Son recours contre cette décision a été rejeté le 13 mars 2003. Le 16 janvier 2006, il s'est marié avec une ressortissante suisse et a obtenu une autorisation de séjour, puis, le 10 janvier 2011, une autorisation d'établissement.
Officiellement séparés depuis le 1er décembre 2011, les époux ont divorcé le 19 juin 2012. Aucun enfant n'est issu de cette union. A._ a signé un contrat de bail avec sa nouvelle compagne, ressortissante macédonienne, le 28 octobre 2011.
Par décision du 11 juillet 2012, le Service des migrations du canton de Neuchâtel (ci-après: le Service cantonal) a prononcé la révocation de l'autorisation d'établissement de A._ en application des art. 51 al. 1 let. a et 63 let. a LEtr et lui a imparti un délai au 30 septembre 2012 pour quitter la Suisse. Il a considéré en substance qu'au vu de l'ensemble des circonstances, au moment de l'octroi de l'autorisation d'établissement, l'intéressé avait fait valoir un mariage qui n'existait que formellement. Cette décision a été confirmée par le Département de l'économie et de l'action sociale du canton de Neuchâtel (ci-après: le Département cantonal) en date du 25 mars 2013. Après avoir procédé à l'audition de son ex-épouse en date du 25 septembre 2013, la Cour de droit public du Tribunal cantonal du canton de Neuchâtel (ci-après: le Tribunal cantonal) a déclaré le recours de A._ irrecevable, pour motif de tardivité. Un délai au 15 février 2014 a été fixé à l'intéressé pour quitter la Suisse.
B.
Le 15 février 2014, A._ a déposé devant le Service cantonal une demande de reconsidération de sa décision du 11 juillet 2012, en se prévalant de l'audition de son ex-épouse du 25 septembre 2013 ainsi que du fait que son employeur était disposé à le réengager. Sa demande a été déclarée irrecevable par décision du 17 mars 2014. Le Département cantonal a rejeté le recours de l'intéressé contre cette décision.
Par arrêt du 17 novembre 2014, le Tribunal cantonal a rejeté le recours de A._. Il a considéré en substance que l'audition de l'ex-épouse du 25 septembre 2013 ne changeait pas la présomption sur laquelle s'était basé le Service cantonal pour rendre sa décision du 11 juillet 2012, selon laquelle l'autorisation d'établissement avait été obtenue frauduleusement.
C.
A._ interjette un "recours de droit public" (recte: recours en matière de droit public) contre l'arrêt du Tribunal cantonal du 17 novembre 2014. Outre l'assistance judiciaire et l'octroi de l'effet suspensif du recours, il demande au Tribunal fédéral, sous suite de frais et dépens, d'annuler l'arrêt du Tribunal cantonal du 17 novembre 2014, d'admettre la demande de reconsidération, de reconsidérer la décision du Service cantonal du 11 juillet 2012 et de l'autoriser à conserver son autorisation d'établissement.
Considérant en droit :
1.
Le Tribunal fédéral examine d'office sa compétence et la recevabilité des recours qui lui sont soumis (cf. art. 29 al. 1 LTF; ATF 136 II 470 consid. 1 p. 472).
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 dans le domaine du droit des étrangers qui concernent une autorisation à laquelle ni le droit fédéral ni le droit international ne donnent droit. Il est cependant recevable contre la révocation d'une autorisation qui déploierait encore ses effets si elle n'avait pas été révoquée (cf. art. 34 al. 1 LEtr; arrêts 2C_1010/2011 du 31 janvier 2012 consid. 1.2; 2C_98/2009 du 10 juin 2009 consid. 1.1).
En l'occurrence, le recours est dirigé contre un arrêt refusant le réexamen d'une décision qui confirmait la révocation de l'autorisation d'établissement du recourant. Ladite autorisation produirait encore ses effets si elle n'avait pas été révoquée. Partant, le recours est recevable en application de l'art. 83 let. c ch. 2 LTF.
1.2. Pour le surplus, l'arrêt attaqué est une décision finale (art. 90 LTF), rendue en dernière instance cantonale par un tribunal supérieur (art. 86 al. 1 let. d et al. 2 LTF). Déposé en temps utile (art. 100 al. 1 LTF) et dans les formes requises (art. 42 LTF) par le destinataire de l'arrêt attaqué qui a qualité pour recourir au sens de l'art. 89 al. 1 LTF, le recours en matière de droit public est par conséquent recevable.
2.
2.1. Le Tribunal fédéral statue sur la base des faits établis par l'autorité précédente (cf. art. 105 al. 1 LTF). Le recours ne peut critiquer les constatations de fait que si les faits ont été établis de façon manifestement inexacte 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 (art. 97 al. 1 LTF), ce que la partie recourante doit démontrer d'une manière circonstanciée, conformément aux exigences de motivation des art. 42 al. 2 et 106 al. 2 LTF (cf. ATF 133 II 249 consid. 1.4.3 p. 254 s.). La notion de "manifestement inexacte" correspond à celle d'arbitraire au sens de l'art. 9 Cst. (ATF 136 II 447 consid. 2.1 p. 450). La partie recourante doit ainsi expliquer de manière circonstanciée en quoi les deux conditions de l'art. 97 al. 1 LTF seraient réalisées, faute de quoi il n'est pas possible de tenir compte d'un état de fait qui diverge de celui qui est contenu dans l'acte attaqué. En particulier, le Tribunal fédéral n'entre pas en matière sur des critiques de type appellatoire portant sur l'état de fait ou sur l'appréciation des preuves (cf. ATF 137 II 353 consid. 5.1 p. 356). Enfin, aucun fait nouveau ni preuve nouvelle ne peut en principe être présenté devant le Tribunal de céans (art. 99 al. 1 LTF).
En l'espèce, le recourant expose son propre état de fait sans mentionner l'art. 97 LTF ni préciser en quoi les faits retenus par l'autorité précédente auraient été établis de manière arbitraire. Dans ces conditions, il n'est pas possible de s'écarter des faits retenus dans l'arrêt attaqué.
2.2. Saisi d'un recours en matière de droit public, le Tribunal fédéral examine d'office le droit fédéral (cf. art. 95 let. a et 106 al. 1 LTF). Sauf exceptions non pertinentes en l'espèce (cf. art. 95 let. c, d et e LTF), l'on ne peut invoquer la violation du droit cantonal en tant que tel devant le Tribunal fédéral (art. 95 LTF a contrario). Il est néanmoins possible de faire valoir que son application consacre une violation du droit fédéral, comme la protection contre l'arbitraire au sens de l'art. 9 Cst. ou la garantie d'autres droits constitutionnels. Le Tribunal fédéral n'examine cependant de tels moyens que s'ils sont formulés conformément aux exigences de motivation qualifiée prévues à l'art. 106 al. 2 LTF (ATF 136 II 304 consid. 2.5 p. 314; arrêt 2C_999/2014 du 15 janvier 2015 consid. 2.2).
3.
Le recourant invoque une violation de son droit d'être entendu tel qu'il est garanti par l'art. 29 al. 2 Cst. Il se plaint de ne pas avoir été entendu personnellement. Il se prévaut également de l'art. 21 de la loi neuchâteloise sur la procédure et la juridiction administratives [LPJA/NE; RSN 152.130], qui dispose que les parties ont le droit d'être entendues.
3.1. Le droit d'être entendu comprend notamment le droit pour l'intéressé de s'exprimer sur les éléments pertinents avant qu'une décision ne soit prise touchant sa situation juridique, de produire des preuves pertinentes, d'obtenir qu'il soit donné suite à ses offres de preuves pertinentes, d'avoir accès au dossier, de participer à l'administration des preuves essentielles ou à tout le moins de s'exprimer sur son résultat, lorsque cela est de nature à influer sur la décision à rendre (ATF 135 I 279 consid. 2.3 p. 282; arrêt 5A_832/2012 du 25 janvier 2013 consid. 4.1). Le droit de faire administrer des preuves découlant du droit d'être entendu n'empêche pas l'autorité de mettre un terme à l'instruction, lorsque les preuves administrées lui ont permis de former sa conviction et que, procédant d'une manière non arbitraire à une appréciation anticipée des preuves qui lui sont encore proposées, elle a la certitude que ces dernières ne pourraient l'amener à modifier son opinion (cf. ATF 138 III 374 consid. 4.3.2 p. 376; 130 II 425 consid. 2.1 p. 429).
3.2. En l'espèce, comme le reconnaît d'ailleurs le recourant lui-même, l'art. 29 al. 2 Cst. n'a pas pour effet de contraindre l'autorité à procéder à l'audition orale d'une partie à la procédure (arrêt 2C_58/2010 du 19 mai 2010 consid. 4.4). Il en va de même de l'art. 21 LPJA/NE qui n'a pas de portée plus large (cf. arrêt 1P.762/1999 du 3 février 2000 consid. 2a). En outre, le recourant a pu faire valoir ses arguments dans les écritures qu'il a déposées, soit dans sa demande de reconsidération ainsi que dans ses recours respectifs auprès du Département cantonal et du Tribunal cantonal, de sorte que l'on voit mal, en l'espèce, ce qu'il aurait pu ajouter utilement lors d'une audition orale.
Le grief du recourant doit donc être rejeté.
4.
Le recourant reproche au Tribunal cantonal de ne pas avoir considéré que l'audition de son ex-épouse constituait un nouveau moyen de preuve faisant ressortir des faits nouveaux. Il invoque une violation de l'art. 29 al. 2 Cst. dans le cadre de l'art. 6 LPJA/NE ainsi que "l'interdiction de l'arbitraire au sens de l'art. 9 Cst."
4.1. Devant le Tribunal fédéral, lorsque l'autorité saisie d'une demande de réexamen entre en matière et rend une nouvelle décision au fond, cette dernière peut faire l'objet d'un recours pour des motifs de fond. Dans cette hypothèse, le litige a pour objet la décision sur réexamen et non pas la décision initiale (arrêt 2C_406/2013 du 23 septembre 2013 consid. 4.1 et les références citées).
Dans une telle situation, le recourant doit se limiter à critiquer l'acte attaqué, en l'occurrence l'arrêt du Tribunal cantonal du 17 novembre 2014, et ne peut pas remettre en cause la décision initiale, à savoir celle du Service cantonal du 11 juillet 2012 révoquant l'autorisation d'établissement (cf. arrêt 2C_406/2013 du 23 septembre 2013 consid. 4.2). Le Tribunal de céans n'entrera donc pas en matière sur les critiques du recourant se rapportant à la décision du 11 juillet 2012 confirmée par le Département cantonal, en particulier les arguments relatifs à son intégration.
Le litige porte dès lors uniquement sur la question de savoir si les déclarations de l'ex-épouse du 25 septembre 2013 constituent un fait nouveau permettant, le cas échéant, de renverser le résultat de la pesée des intérêts (cf. arrêt 2C_406/2013 du 23 septembre 2013 consid. 4.2).
4.2. Les autorités administratives sont tenues de réexaminer leurs décisions si une disposition légale expresse ou si une pratique administrative constante les y oblige (cf. arrêts 2C_1224/2013 du 12 décembre 2014 consid. 4.1 et 2C_1010/2011 du 31 janvier 2012 consid. 2.2). Tel est le cas de l'art. 6 al. 1 LPJA/NE appliqué par les autorités cantonales qui traite des motifs de reconsidération ou de révision des décisions et qui dispose notamment que l'autorité peut reconsidérer une décision lorsque des faits nouveaux se sont produits ou ont été découverts (let. a).
La jurisprudence a, en outre, déduit de l'art. 29 al. 1 et 2 Cst. l'obligation, pour l'autorité administrative, de se saisir d'une demande de réexamen lorsque les circonstances se sont modifiées de façon notable depuis la première décision ou lorsque le requérant invoque des faits essentiels et des moyens de preuve nouveaux qu'il ne connaissait pas ou a été dans l'impossibilité de faire valoir dans la procédure antérieure (ATF 124 II 1 consid. 3a p. 6; arrêt 2C_1224/2013 du 12 décembre 2014 consid. 4.1 et les références citées). Le réexamen de décisions entrées en force ne saurait toutefois servir à remettre sans cesse en cause des décisions exécutoires ou à détourner les délais prévus pour les voies de droit ordinaires (ATF 136 II 177 consid. 2.1 p. 181; arrêt 2C_1224/2013 du 12 décembre 2014 consid. 4.4 et les références citées).
4.3. Dans la mesure où le recourant se borne à reprocher au Tribunal cantonal d'avoir considéré que l'audition de l'ex-épouse ne constituait pas "un nouveau moyen de preuve faisant ressortir des faits nouveaux" sans critiquer l'acte attaqué ni expliquer en quoi l'instance précédente aurait appliqué l'art. 6 LPJA/NE de manière arbitraire, la recevabilité du grief apparaît douteuse (cf. supra consid. 2.2). Cette question peut toutefois rester ouverte dans la mesure où le grief doit de toute façon être rejeté.
4.4. Le recourant se plaint du fait que les autorités n'ont pas entendu son ex-épouse et ne se sont pas prononcées sur cette "offre de preuve". Il convient de relever que c'est précisément suite au recours qu'il a interjeté dans le cadre de la procédure ordinaire relative à la révocation de son autorisation d'établissement - et conformément à sa demande - que le Tribunal cantonal a procédé à l'audition de son ex-épouse, avant de constater que le recours interjeté par l'intéressé était tardif. En réalité, le recourant se prévaut aujourd'hui - par la voie de la reconsidération - de déclarations dont il aurait pu se prévaloir dans la procédure ordinaire de recours s'il n'avait pas déposé son recours tardivement.
4.5. Quoi qu'il en soit, dans son arrêt, le Tribunal cantonal est néanmoins entré en matière sur la demande de reconsidération mais a jugé que l'élément nouveau invoqué par le recourant ne modifiait pas l'appréciation des autorités cantonales. Contrairement à ce que soutient le recourant, le Tribunal cantonal a motivé sa décision. En effet, il a considéré que les déclarations de l'ex-épouse - soit que le couple ne s'entendait plus, que la décision de se séparer avait été prise rapidement, qu'elle savait que son ex-époux avait une amie, que cela n'avait pas joué de rôle dans leur séparation et qu'elle ignorait la date de cette nouvelle relation - ne changeaient rien à l'enchaînement rapide des événements fondant la présomption sur laquelle s'était basé le Service cantonal pour rendre sa décision révoquant l'autorisation d'établissement au motif que celle-ci avait été obtenue frauduleusement par l'intéressé. Le Tribunal cantonal a également relevé à juste titre que, dans son audition, l'ex-épouse n'a pas indiqué quels auraient été les motifs de la rapide détérioration du lien conjugal (cf. arrêt 2C_682/2012 du 7 février 2013 consid. 4.1).
Compte tenu de ces éléments, le Tribunal n'a pas versé dans l'arbitraire ni violé le droit d'être entendu du recourant en considérant que l'audition de son ex-épouse n'était pas propre à modifier l'appréciation faite par le Service cantonal dans sa décision du 11 juillet 2012 et confirmée par le Département cantonal.
5.
Les considérants qui précèdent conduisent au rejet du recours, dans dans la mesure où il est recevable.
La demande d'effet suspensif est devenue sans objet. 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. 66 al. 1 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 en matière de droit public est rejeté dans la mesure où il est recevable.
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é à la mandataire du recourant, au Service des migrations, au Département de l'économie et de l'action sociale et au Tribunal cantonal de la République et canton de Neuchâtel, Cour de droit public, ainsi qu'au Secrétariat d'Etat aux migrations.
Lausanne, le 13 février 2015
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président : Zünd
La Greffière : Thalmann