Citation: 2C_22/2019 E. A

A.a. A.A.________, ressortissant macédonien né en 1969, a épousé dans son pays, le 21 février 2005, E.________, ressortissante suisse née en 1979. A.A.________ est entré en Suisse le 7 novembre 2005 et a obtenu, dans le canton de Berne, une autorisation de séjour régulièrement renouvelée. Le 17 décembre 2010, il s'est vu délivrer une autorisation d'établissement. A.b. Depuis son arrivée en Suisse, A.A.________ a alterné les périodes de chômage et l'exercice d'emplois non qualifiés. Il a bénéficié de l'aide sociale durant plusieurs années pour un montant totalisant 42'918 fr. 80 et a contracté des dettes pour un total de 59'429 fr. 35, dont 51'127 fr. 55 d'actes de défaut de biens. Il a par ailleurs été condamné à deux reprises pour infractions en matière de circulation routière. A.c. Le 16 août 2011, A.A.________ a annoncé son arrivée dans le canton de Neuchâtel au 30 mars 2011. Le 26 août 2011, il a signé avec E.________, devant le tribunal compétent, une convention de séparation mentionnant le 1er août 2010 comme date de séparation et autorisant les époux à vivre séparés pour une durée indéterminée. Le jugement de divorce est entré en force le 22 février 2012. A.d. Par décision du 27 février 2012, le Service des migrations de la République et canton de Neuchâtel (ci-après: le Service cantonal) a refusé de délivrer une autorisation d'établissement à A.A.________ dans le canton de Neuchâtel, au motif que l'intéressé avait obtenu une autorisation d'établissement dans le canton de Berne en dissimulant aux autorités compétentes que son mariage n'existait plus que formellement. Par décision du 4 juin 2013, le Département de l'économie (actuellement le Département de l'économie et de l'action sociale de la République et canton de Neuchâtel; ci-après: le Département cantonal) a admis le recours interjeté par A.A.________ contre cette décision.