Faits:
A.
X._, ressortissant du Kosovo, né en 1971, est entré en Suisse le 19 avril 1998 et a déposé une demande d'asile, rejetée le 10 août 1999. A la suite d'un accident de voiture en 1998, il a perdu sa première épouse et a été blessé. Il s'est remarié avec une ressortissante suisse et a obtenu une autorisation de séjour dans les cantons d'Argovie, puis de Berne, où une autorisation d'établissement lui a été délivrée le 27 mars 2006. Un enfant prénommé A._ est né de cette union le 16 juillet 2002. Le divorce des époux a été prononcé le 23 janvier 2009.
Le 23 décembre 2009, X._ a épousé une ressortissante serbe, Y._, titulaire d'une autorisation d'établissement dans le canton de Neuchâtel. Une enfant prénommée B._ est née de cette union le 4 décembre 2010.
Par décision du 20 décembre 2010, le Service des migrations du canton de Neuchâtel (ci-après: le Service des migrations) a refusé d'accorder une autorisation d'établissement à X._, en retenant principalement qu'il émargeait à l'aide sociale, ainsi que son épouse, qu'il ne faisait pas ménage commun avec celle-ci et que son droit de visite sur son fils A._ pourrait s'exercer depuis l'étranger.
B.
X._ a recouru contre cette décision auprès du Département de l'économie du canton de Neuchâtel, en faisant valoir que le couple n'avait pas fait ménage commun dans un premier temps en raison des disputes de son fils et d'une nièce dont son épouse avait la garde, mais que les époux vivaient maintenant ensemble.
Par décision du 18 novembre 2011, le Département a rejeté le recours. Le 22 décembre 2011, X._ a demandé la reconsidération de cette décision, en alléguant que son épouse venait de trouver un emploi, que son revenu couvrirait alors une grande partie des besoins de la famille et qu'ils déménageraient dans un appartement moins cher. Il a également recouru auprès de la Cour de droit public du Tribunal cantonal du canton de Neuchâtel (ci-après: le Tribunal cantonal) et produit un rapport médical faisant état de problèmes physiques et psychiques, qui avaient nécessité une hospitalisation en août 2011, et a indiqué vouloir demander des prestations de l'assurance-invalidité.
C.
Par arrêt du 26 mars 2013, le Tribunal cantonal a rejeté le recours formé par X._. Il a retenu en substance que le droit à un changement de canton avait été refusé à juste titre au recourant, car celui-ci avait accumulé, sur cinq ans, une dette d'assistance supérieure à 100'000 fr., alors qu'il était partiellement apte à travailler, démontrant par-là une absence d'intégration dans le monde du travail et la société en général. Rien ne laissait supposer non plus qu'il puisse se passer à l'avenir de l'aide sociale, dès lors que le revenu mensuel net de son épouse, de l'ordre de 2'200 fr., ne suffirait pas à couvrir les charges de la famille. Sous l'angle de l'art. 8 CEDH, la cour cantonale a considéré que le recourant était titulaire d'une autorisation d'établissement dans le canton de Berne et qu'il pourrait continuer à avoir des contacts personnels avec sa famille. En outre, un renvoi au Kosovo était possible du moment qu'il avait gardé des liens avec son pays d'origine et que ses traitements médicaux pourraient être pris en charge dans ce pays.
D.
X._ forme un recours en matière de droit administratif (sic), subsidiairement un recours constitutionnel subsidiaire, et conclut, avec suite de frais et dépens, à l'annulation de l'arrêt du Tribunal cantonal du 26 mars 2013 et à l'octroi d'une autorisation d'établissement dans le canton de Neuchâtel ou, à titre subsidiaire, au renvoi de l'affaire à l'autorité de première instance pour nouvelle décision dans le sens des considérants. Il présente également une demande d'assistance judiciaire.
Le Tribunal cantonal se réfère à son arrêt et conclut, tardivement, au rejet du recours. Le Département conclut au rejet du recours, de même que le Service des migrations dans la mesure où celui-ci est recevable. De son côté, l'Office fédéral des migrations propose de rejeter le recours.

Considérant en droit:
1.
1.1. Selon l'art. 83 let. c LTF, le recours en matière de droit public est irrecevable contre les décisions en matière de droit des étrangers qui concernent le déplacement de la résidence dans un autre canton, et ce même si l'étranger a un droit au changement de canton (arrêts 2D_17/2011 du 26 août 2011, consid. 1.1; 2C_886/2008 du 4 mai 2009 consid. 2 et les références citées).
Il s'ensuit que le présent recours est irrecevable comme recours en matière de droit public. Le Tribunal fédéral peut cependant le traiter comme recours constitutionnel subsidiaire, s'il en remplit les conditions, ainsi que l'a désigné subsidiairement le recourant. La fausse désignation comme recours en matière de droit administratif à titre principal n'est à cet égard pas pertinente (cf. <ref-ruling> consid. 1.2 p. 302).
1.2. L'art. 37 al. 3 de la loi fédérale sur les étrangers (LEtr; RS 142.20) dispose que le titulaire d'une autorisation d'établissement a droit au changement de canton s'il n'existe aucun motif de révocation au sens de l'art. 63 LEtr. Comme motif de révocation, l'art. 63 al. 1 let. c LEtr mentionne notamment le fait que le requérant lui-même ou une personne dont il a la charge dépende durablement et dans une large mesure de l'aide sociale. Savoir si l'autorisation sollicitée peut être refusée pour un tel motif est toutefois une question de fond et non de recevabilité. Le recourant peut ainsi faire valoir un intérêt juridique, au sens de l'<ref-law>, à la modification de la décision cantonale.
1.3. Pour le surplus, le recours est dirigé contre un jugement final (art. 117 et 90 LTF) rendu par un tribunal supérieur statuant en dernière instance cantonale (art. 114 et 86 LTF) et a été déposé dans le délai (art. 117 et 100 al. 1 LTF) et la forme (<ref-law>) prévus par la loi. Il est donc en principe recevable au regard des <ref-law>.
1.4. Le recours constitutionnel subsidiaire peut être formé pour violation des droits constitutionnels (<ref-law>). Le Tribunal fédéral examine la violation de droits fondamentaux, ainsi que celle de dispositions de droit cantonal et intercantonal, seulement lorsque ce grief a été invoqué et motivé de façon détaillée par la partie recourante (art. 106 al. 2 et 117 LTF; <ref-ruling> consid. 3.2 p. 88). Il statue sur la base des faits constatés dans la décision attaquée et ne peut rectifier ou compléter les constatations de l'autorité précédente que si les faits ont été établis en violation des droits constitutionnels (art. 118 al. 2 et 116 LTF), ce qu'il appartient au recourant de faire valoir de manière claire et précise (<ref-ruling> consid. 4.1 p. 235; <ref-ruling> consid. 1.5 p. 674, 232 consid. 1.2 p. 234; <ref-ruling>, consid. 3.2 p. 445).
2.
Le recourant se plaint d'une violation du droit d'être entendu sous l'angle de l'art. 29 al. 2 Cst., en relation avec les art. 13 et 5 al. 1 Cst., ainsi que de l'art. 8 CEDH, pour défaut de motivation de l'arrêt attaqué. Il reproche aux premiers juges de n'avoir pas procédé à une pesée correcte des intérêts en présence au regard des dispositions précitées.
Ce grief doit être examiné en premier lieu. En effet, compte tenu du caractère formel du droit d'être entendu, si la violation devait être avérée, elle entraînerait l'annulation de l'arrêt attaqué quelles que soient les chances de succès du recours sur le fond (<ref-ruling> consid. 2.2 p. 197; <ref-ruling> consid. 2.6.1 p. 285).
2.1. Le droit d'être entendu découlant de l'art. 29 al. 2 Cst. impose notamment à l'autorité de motiver sa décision. Cette obligation est remplie lorsque l'intéressé est mis en mesure d'en apprécier la portée et de la déférer à une instance supérieure en pleine connaissance de cause. Il suffit que l'autorité mentionne au moins brièvement les motifs qui l'ont guidée et sur lesquels elle s'est fondée pour rendre sa décision. Elle n'est pas tenue de se prononcer sur tous les moyens des parties et peut ainsi se limiter aux points essentiels pour la décision à rendre (<ref-ruling> consid. 3.2 p. 270; <ref-ruling> consid. 5.2 p. 236; <ref-ruling> consid. 3.3.1 p. 677).
2.2. Selon l'art. 66 de l'ordonnance fédérale du 24 octobre 2007 relative à l'admission, au séjour et à l'exercice d'une activité lucrative (OASA; RS 142.201), les étrangers ne peuvent disposer d'une autorisation de séjour, de courte durée ou d'établissement que dans un seul canton; les autorisations sont valables sur le territoire du canton qui les a délivrées. L'étranger qui souhaite changer de canton doit requérir une autorisation de changement de canton (art. 67 al. 1 OASA). L'autorisation prend fin lorsque l'étranger obtient une autorisation dans un autre canton (art. 61 al. 1 let. b LEtr). Comme mentionné, l'art. 37 al. 3 LEtr dispose que le titulaire d'une autorisation d'établissement a droit au changement de canton s'il n'existe aucun motif de révocation au sens de l'art. 63 LEtr, lequel prévoit, à son alinéa 1 let. c, la dépendance durable et dans une large mesure à l'aide sociale.
La jurisprudence, se fondant notamment sur le Message du 24 octobre 2007 concernant la loi sur les étrangers (FF 2002 3469) et sur la doctrine, a précisé que l'autorisation ne pourra être refusée dans le nouveau canton au seul motif que le requérant peut rester dans l'actuel canton de domicile. Il doit exister un motif de révocation justifiant un renvoi de Suisse. Pour cette raison, le nouveau canton est tenu d'examiner s'il existe un motif de révocation et si une expulsion (sous le nouveau droit, un renvoi) de Suisse constituerait une mesure proportionnelle (arrêt précité 2C_17/2011 du 26 août 2011 consid. 3.3). Cet arrêt est aussi conforme aux critères déterminants découlant de l'art. 8 § 2 CEDH, qui doivent aussi être respectés en l'occurrence, la décision attaquée ayant pour effet de priver le recourant d'une vie familiale commune. Dans un arrêt récent (Hansanbasic c. Suisse du 11 juin 2013, n o 52166/09), la Cour européenne des droits de l'homme a rappelé que le bien-être économique du pays était un but légitime justifiant une ingérence dans l'exercice du droit au respect de la vie privée familiale, de sorte que l'endettement et la dépendance à l'assistance publique des requérants pouvaient être pris en considération. Elle a cependant précisé que ces éléments ne constituaient qu'un aspect parmi les autres critères qui devaient être pris en compte dans l'examen sous l'angle de l'art. 8 § 2 CEDH (arrêt précité § 59 et les références citées), comme par exemple la situation de toutes les personnes concernées, conjoint et enfants, ou les éléments d'ordre médical (arrêt précité § 53 et 54 avec les références à l'arrêt Emre c. Suisse du 22 mai 2008, n o 4234/04 § 81-83). D'une manière générale, l'autorité de police des étrangers doit en outre faire preuve de beaucoup de retenue dans l'application des révocations d'autorisations d'établissement pour cause de dépendance à l'aide sociale (cf. FF 2002 3469, p. 3566; arrêt 2C_268/2011 du 22 juillet 2011, consid. 7.1).
Il en découle que l'autorité cantonale devait non seulement constater la dépendance du recourant à l'aide sociale, mais était également tenue d'examiner si cette dépendance constituait un motif suffisant pour justifier la révocation de son autorisation d'établissement, compte tenu de l'ensemble des circonstances, en particulier de la situation familiale du recourant.
2.3. Sous l'angle de la proportionnalité, le Tribunal cantonal a considéré que, comme l'autorisation d'établissement dans le canton de Berne était maintenue, le recourant pourrait conserver des contacts personnels avec sa famille et bénéficier de périodes de calme que nécessitent ses traitements médicaux. En outre, un renvoi au Kosovo pourrait être exécuté, dès lors qu'il avait gardé des liens dans son pays d'origine et qu'il aurait la possibilité d'y poursuivre ses traitements médicaux. Or de tels éléments sont insuffisants dans le cadre de l'examen de la proportionnalité, qui implique de procéder à la pesée de l'intérêt public au refus de l'autorisation et l'intérêt privé à l'obtention du titre de séjour (<ref-ruling> consid. 6.5.1 p. 132; <ref-ruling> consid. 5.1 p. 287; <ref-ruling> consid. 2.1 p. 155 et les référence citées; voir aussi arrêt 2C_240/2012 du 15 mars 2013, consid. 2.4 et 2.5, destiné à la publication). Il appartenait ainsi à la juridiction cantonale d'évaluer les conséquences du refus d'autorisation sur la vie privée et familiale du recourant, qui habite actuellement à Z._ avec sa femme, titulaire d'une autorisation d'établissement dans le canton de Neuchâtel, et sa fille B._, âgée de deux ans et 20 mois, non seulement par rapport à la possibilité, pour lui, de vivre dans le canton de Berne, mais aussi par rapport à son renvoi de Suisse. En se bornant à constater qu'un retour du recourant dans son pays d'origine était possible, sans autre précision quant à sa famille, le Tribunal cantonal n'a pas procédé à une pesée correcte des intérêts en présence, ainsi que l'exige l'art. 8 § 2 CEDH. Les éléments figurant au dossier ne permettent d'ailleurs pas d'examiner la situation du recourant selon tous les critères à prendre en considération dans un tel cas. La relation qu'il a avec son fils A._, qui vit avec sa mère dans le canton de Berne et sur lequel il semble avoir un droit de visite n'a pas non plus été examinée.
Il s'ensuit que le grief de violation du droit d'être entendu pour défaut de motivation de l'arrêt attaqué est fondé, ce qui entraîne l'admission du recours (<ref-ruling> consid. 2.7 p. 199).
3.
Au vu de ce qui précède, le recours, traité comme recours constitutionnel subsidiaire, doit être admis et l'affaire renvoyée au Tribunal cantonal pour nouvelle instruction et nouveau jugement.
Compte tenu de l'issue du recours, la demande d'assistance judiciaire présentée par le recourant devient sans objet.
L'arrêt sera ainsi rendu sans frais (<ref-law>) et le canton de Neuchâtel devra verser au mandataire du recourant une indemnité à titre de dépens (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1.
Le recours en matière de droit public est irrecevable.
2.
Le recours constitutionnel subsidiaire est admis et la cause est renvoyée au Tribunal cantonal pour nouvelle instruction et nouveau jugement.
3.
Il n'est pas perçu de frais judiciaires.
4.
Le canton de Neuchâtel versera au mandataire du recourant une indemnité de 2'000 fr. à titre de dépens.
5.
Le présent arrêt est communiqué au mandataire du recourant, au Service des migrations, au Département de l'économie et au Tribunal cantonal de la République et canton de Neuchâtel, Cour de droit public, ainsi qu'à l'Office fédéral des migrations.
Lausanne, le 13 septembre 2013
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: Zünd
La Greffière: Rochat