Faits : 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. B. B.a. B._ et ses deux enfants, C.A._, née en 2001, et D.A._, né en 2007, tous ressortissants macédoniens, sont entrés en Suisse le 12 mars 2016. B._ a déposé une demande d'autorisation de séjour de courte durée en vue de son mariage avec A.A._ et celui-ci a demandé le regroupement familial en faveur de sa future épouse et des deux enfants. Le couple s'est marié en Suisse le 20 mai 2016. B.b. A.A._ est le père de C.A._. Les parents ont expliqué avoir entretenu une relation à partir de l'année 2000. Ils s'étaient séparés au cours de l'année 2002, à la suite de pressions familiales, et n'avaient repris leur relation qu'au mois de mars 2016. A.A._ avait, ensuite de leur séparation, toujours entretenu des relations avec leur fille ainsi que contribué à son entretien. A.A._ a reconnu la paternité de D.A._ le 25 avril 2016. Il a tout d'abord soutenu ne pas être le père biologique de cet enfant et l'avoir reconnu dans le but de lui permettre de venir en Suisse. Un rapport d'expertise en lien de parenté établi le 21 mars 2017 a confirmé la probabilité de cette paternité comme étant supérieure à 99.999 %. A.A._ et B._ ont alors expliqué que cet enfant avait été conçu accidentellement lors d'un séjour du premier en Macédoine. Ils avaient toutefois ignoré que A.A._ était le père de D.A._, sa mère ayant à l'époque également fréquenté un autre homme. B.c. Par décision du 8 juin 2017, le Service cantonal a révoqué l'autorisation d'établissement de A.A._ et classé les demandes de regroupement familial déposées par ce dernier en faveur de son épouse et de leurs deux enfants. Le Département cantonal a rejeté le recours interjeté par les intéressés contre cette décision par prononcé du 29 mars 2018. Par arrêt du 22 novembre 2018, le Tribunal cantonal de la république et canton de Neuchâtel, Cour de droit public (ci-après: le Tribunal cantonal) a rejeté le recours dirigé contre ce prononcé. C. Agissant par la voie du recours en matière de droit public, A.A._ (ci-après: le recourant 1), B.A._ (ci-après: la recourante 2), C.A._ (ci-après: la recourante 3) et D.A._ (ci-après: le recourant 4) demandent en substance au Tribunal fédéral, outre le bénéfice de l'assistance judiciaire et l'octroi de l'effet suspensif à leur recours, l'annulation de la révocation de l'autorisation d'établissement du recourant 1 et la délivrance d'autorisations de séjour en faveur des recourants 2, 3 et 4, subsidiairement le renvoi de la cause au Tribunal cantonal pour nouvelle décision dans le sens des considérants. Le Président de la Cour de céans a admis la requête d'effet suspensif. Le Tribunal fédéral a par ailleurs renoncé provisoirement à demander une avance de frais aux recourants et informé ces derniers qu'il serait statué ultérieurement sur leur demande d'assistance judiciaire. Le Tribunal cantonal, le Département cantonal et le Service cantonal ont conclu au rejet du recours.