Faits:
A.
A._, ressortissant du Bénin, né en 1975, est entré en Suisse au mois de juillet 2004 et a déposé une demande d'asile, définitivement rejetée par la Commission suisse de recours en matière d'asile le 28 octobre 2004. Il a bénéficié d'une formation en informatique dans le cadre de l'aide au retour et l'Office cantonal de la population du canton de Genève a prolongé son délai de départ à plusieurs reprises, la dernière fois jusqu'au 15 février 2007.
Le 2 février 2007, A._ a épousé, à C._, une ressortissante suisse, B._, mère de trois enfants, et a été mis au bénéfice d'une autorisation de séjour pour regroupement familial dans le canton de Neuchâtel, prolongée la dernière fois jusqu'au 2 février 2012. Les époux se sont séparés pour la deuxième fois le 30 juin 2011, puis ont été autorisés à vivre séparés par décision du Tribunal régional du Littoral et Val-de-travers du 23 novembre 2011. Durant leur mariage, les époux avaient bénéficié de l'aide sociale pour un montant de 146'307 fr.55.
B.
Par décision du 21 mars 2012, le Service des migrations du canton de Neuchâtel a refusé de prolonger l'autorisation de séjour de A._, au motif que son intégration ne pouvait être considérée comme réussie, qu'il émargeait totalement à l'aide sociale et qu'au vu des nombreux séjours qu'il avait effectués au Bénin, où il avait trois enfants d'une précédente union, la question de son centre d'intérêt pouvait se poser. Le recours déposé par l'intéressé auprès du Département de l'économie et de l'action sociale du canton de Neuchâtel (ci-après: le Département) a été rejeté par décision du 31 décembre 2012.
Statuant le 6 août 2013 sur le recours de A._, le Tribunal cantonal du canton de Neuchâtel l'a rejeté, avec suite de frais. Il a retenu en bref que les époux étaient séparés depuis le 30 juin 2011 et que leur mariage ne subsistait plus que formellement. Au vu de son parcours professionnel, l'intéressé ne pouvait pas non plus se prévaloir d'une intégration réussie au sens de l'art. 50 al. 1 let. a de la loi fédérale sur les étrangers (LEtr; RS 142.20).
C.
Agissant par la voie du recours en matière de droit public, A._ conclut, sous suite de frais et dépens, à l'annulation de l'arrêt du Tribunal cantonal du 6 août 2013, subsidiairement, au renvoi à cette autorité pour nouveau jugement.
Le Tribunal cantonal, le Service des migrations et le Département se réfèrent à l'arrêt attaqué et concluent au rejet du recours. L'Office fédéral des migrations propose également de rejeter le recours.
D.
Par ordonnance présidentielle du 19 septembre 2013, l'effet suspensif a été attribué au recours. A sa demande, A._ a aussi été autorisé à verser l'avance de frais en trois mensualités, par ordonnance présidentielle du 4 octobre 2013.

Considérant en droit:
1.
1.1. En vertu de l'art. 83 let. c ch. 2 LTF, le recours 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. En l'espèce, l'union conjugale du recourant avec une ressortissante suisse ne subsistant plus que formellement, celui-ci ne peut pas déduire un droit à une autorisation de séjour de l'art. 42 al. 1 LEtr. En revanche, dans la mesure où le recourant soutient de manière plausible qu'il réalise les conditions de l'art. 50 al. 1 let. a LEtr, il a potentiellement un droit à l'obtention d'une autorisation de séjour en vertu de cette disposition, de sorte que son recours en matière de droit public échappe au motif d'irrecevabilité prévu à l'art. 83 let. c ch. 2 LTF (<ref-ruling> consid. 3.3 p. 501, 177 consid. 1.1 p. 179).
1.2. Au surplus, déposé en temps utile (<ref-law>) et dans les formes prescrites par la loi (<ref-law>), par le destinataire de l'arrêt attaqué qui a un intérêt digne de protection à son annulation ou à sa modification (<ref-law>), le présent recours, dirigé contre une décision d'une autorité judiciaire cantonale supérieure (art. 86 al. 1 let. d et al. 2 LTF), est recevable.
2.
Invoquant l'<ref-law>, le recourant se plaint de l'appréciation arbitraire des preuves et des constatations manifestement inexactes des faits par l'instance précédente.
2.1. Le Tribunal fédéral se fonde sur les faits constatés par l'autorité précédente (cf. <ref-law>), à moins que ceux-ci n'aient été établis de façon manifestement inexacte - notion qui correspond à celle d'arbitraire (cf. <ref-ruling> consid. 7.1 p. 51; <ref-ruling> consid. 4.2 p. 560) - ou en violation du droit au sens de l'<ref-law> (cf. <ref-law>), et pour autant que la correction du vice soit susceptible d'influer sur le sort de la cause (cf. <ref-law>).
Lorsque la partie recourante - comme c'est le cas en l'espèce - s'en prend à l'appréciation des preuves et à l'établissement des faits, la décision n'est arbitraire que si le juge n'a manifestement pas compris le sens et la portée d'un moyen de preuve, s'il a omis, sans raison sérieuse, de tenir compte d'un moyen important propre à modifier la décision attaquée ou encore si, sur la base des éléments recueillis, il a fait des déductions insoutenables (cf. ATF <ref-ruling> consid. 4.2 p. 560; <ref-ruling> consid. 2.1 p. 9; arrêt 2C_177/2013 du 6 juin 2013, consid. 2.1).
2.2. Le recourant reproche au Tribunal cantonal d'avoir retenu arbitrairement qu'il n'avait jamais été indépendant financièrement et qu'il ne pouvait s'assumer sans les indemnités de l'assurance-chômage, alors qu'il a été engagé par l'Etablissement vaudois d'accueil des migrants (ci-après: l'EVAM) depuis le 1er avril 2012 et ne touche plus l'assistance sociale depuis le 29 février 2012.
Contrairement à ce que soutient le recourant, la juridiction cantonale a tenu compte des éléments précités dans son appréciation de la situation financière de l'intéressé, qu'elle devait considérer globalement et non seulement au jour de sa décision. Elle a ainsi retenu que le recourant n'avait jamais eu un emploi stable à plein temps, ou lui permettant de subvenir à ses besoins ou à ceux de sa famille, et qu'il avait toujours été soutenu partiellement ou totalement par l'aide sociale. Elle en a déduit que son emploi actuel à 50% à l'EVAM ne suffisait pas pour qu'il puisse s'assumer financièrement et qu'aucun élément ne permettait de dire comment il subviendrait à ses besoins à la fin des indemnités de chômage qui lui sont versées. Or, le recourant n'explique pas en quoi cette appréciation serait arbitraire et ne correspondrait pas à la réalité de son parcours professionnel. Il ne prétend pas davantage que son salaire actuel suffirait à couvrir ses besoins et à rembourser ses dettes, sans le versement des indemnités de chômage. Comme le Tribunal cantonal l'a relevé à juste titre, il n'a donc fourni aucun indice qui aurait permis de penser qu'il était disposé à augmenter son taux d'activité pour devenir indépendant financièrement à la fin de délai-cadre où il ne toucherait plus les indemnités de chômage. Il s'ensuit que les premiers juges n'ont nullement établi les faits ni apprécié les preuves de façon arbitraire en retenant que le recourant n'avait jamais pu s'assumer lui-même financièrement. Le recours doit donc être rejeté sur ce point.
3.
Au fond, le recourant reproche aux premiers juges d'avoir considéré à tort qu'il ne pouvait se prévaloir d'une intégration réussie, et partant, bénéficier de la prolongation de son autorisation de séjour.
3.1. Selon l'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 (<ref-ruling> consid. 3.3.3 p. 119).
En l'espèce, les autorités précédentes ont admis que l'union conjugale avait duré plus de trois ans. Seule demeure donc litigieuse la question de l'intégration réussie.
3.2. Le principe de l'intégration doit permettre aux étrangers dont le séjour est légal et durable de participer à la vie économique, sociale et culturelle de la Suisse (art. 4 al. 2 LEtr; cf. <ref-ruling> consid. 4.1 p. 4). D'après l'art. 77 al. 4 de l'ordonnance du 24 octobre 2007 relative à l'admission, au séjour et à l'exercice d'une activité lucrative (OASA; RS 142.201), un étranger s'est bien intégré, au sens de l'art. 50 al. 1 let. a LEtr, notamment lorsqu'il respecte l'ordre juridique suisse et les valeurs de la Constitution fédérale (let. a) et qu'il manifeste sa volonté de participer à la vie économique et d'apprendre la langue nationale parlée au lieu de domicile (let. b). Selon l'art. 4 de l'ordonnance du 24 octobre 2007 sur l'intégration des étrangers (OIE; RS 142.205), la contribution des étrangers à l'intégration se manifeste notamment par le respect de l'ordre juridique et des valeurs de la Constitution fédérale (let. a), par l'apprentissage de la langue nationale parlée sur le lieu de domicile (let. b), par la connaissance du mode de vie suisse (let. c) et par la volonté de participer à la vie économique et d'acquérir une formation (let. d). Le Tribunal fédéral a précisé que l'adverbe "notamment", qui est employé tant à l'art. 77 al. 4 OASA qu'à l'<ref-law>, illustre le caractère non exhaustif des critères d'intégration qui sont énumérés par ces dispositions et met aussi en exergue le fait que la notion "d'intégration réussie" doit s'examiner à l'aune d'une appréciation globale des circonstances (arrêts 2C_749/2011 du 20 janvier 2012, consid. 3.2; 2C_427/2011 du 26 octobre 2011, consid. 5.2; 2C_839/2010 du 25 février 2011, consid. 7.1.2).
Un étranger qui obtient, même au bénéfice d'un emploi à temps partiel, p. ex. en tant que nettoyeur, un revenu de l'ordre de 3'000 fr. mensuels qui lui permet de subvenir à ses besoins jouit d'une situation professionnelle stable (arrêt 2C_426/2011 du 30 novembre 2011, consid. 3.3). Il importe peu que l'indépendance financière résulte d'un emploi peu qualifié. L'intégration réussie au sens de l'art. 50 al. 1 let. a LEtr n'implique en effet pas nécessairement la réalisation d'une trajectoire professionnelle particulièrement brillante au travers d'une activité exercée sans discontinuité (arrêt précité 2C_749/2011, consid. 3.3). L'essentiel en la matière est que l'étranger subvienne à ses besoins, n'émarge pas à l'aide sociale et ne s'endette pas (cf. arrêt 2C_430/2011 du 11 octobre 2011, consid. 4.2). Il n'y a en revanche pas d'intégration réussie lorsqu'il n'exerce pas d'activité lucrative qui lui permette de couvrir ses besoins et qu'il dépend des prestations sociales pendant une période relativement longue (arrêt 2C_930/2012 du 10 janvier 2013, consid. 3.1 et les arrêts cités).
Dans l'examen de ces critères d'intégration, les autorités compétentes disposent d'un large pouvoir d'appréciation que le Tribunal fédéral ne revoit qu'avec retenue (cf. art. 54 al. 2 et 96 al. 1 LEtr; <ref-law>; arrêts précités 2C_930/2012 consid. 3.1; 2C_749/2011 consid. 3.2 et les arrêts cités).
3.3. En l'espèce, le Tribunal cantonal a admis que le recourant savait le français, langue officielle du Bénin, et qu'il n'avait pas de casier judiciaire. L'intéressé avait toutefois fait l'objet de huit poursuites, dont sept s'étaient soldées par des actes de défaut de biens pour un montant total de 3'864 fr. 95. A cet égard, les pièces nouvelles que le recourant produit pour démontrer qu'il est en train de régulariser sa situation et de désintéresser l'ensemble de ses créanciers sont irrecevables (<ref-law>). Au surplus, depuis le mariage, jusqu'à la séparation des époux au 30 juin 2011, la famille avait aussi été soutenue par l'aide sociale pour un montant s'élevant à 146'307 fr. 55, auquel s'ajoutaient les aides encore versées après la séparation. Retraçant son parcours professionnel, la juridiction cantonale a constaté que le recourant avait effectué, d'octobre 2008 à février 2011, diverses missions à temps partiel, de 7 à 16 heures par semaine, pour l'entreprise Dosim SA. Dès le 1er avril 2011, il avait été engagé à temps partiel pour la société Hotelis, à Lausanne, puis par l'EVAM dès le 18 janvier 2012 en qualité d'encadrant de cuisine, engagement qui avait passé à 50% pour une durée indéterminée à partir du 1er avril 2012. Sur ce point, le recourant se borne à soutenir qu'il a réussi à se passer de l'aide sociale depuis le 29 février 2012 et qu'il subvient maintenant à ses besoins. Selon l'arrêt attaqué toutefois, tel est le cas grâce aux indemnités de chômage versées (cf. supra consid. 2.2). Il faut donc admettre que son travail actuel à 50% est insuffisant pour lui permettre de s'assumer seul à long terme et de rembourser ses dettes. Pour le reste, le recourant n'explique pas pourquoi il n'a jamais travaillé à temps complet et n'a pas vraiment fait d'efforts pour s'intégrer professionnellement, préférant être assisté avant et durant son mariage. Sur le plan social, le recourant ne fournit pas non plus d'indices d'une intégration réussie en dehors des liens qu'il a maintenus avec ses compatriotes en Suisse et au Bénin, où vivent d'ailleurs ses trois enfants. Le fait de participer à des activités paroissiales, pour autant qu'il soit attesté, ne suffit pas.
3.4. Au vu de tous ces éléments, le Tribunal cantonal n'a pas violé le droit fédéral en retenant que le recourant ne pouvait pas se prévaloir d'une intégration réussie au sens de l'art. 50 al. 1 let. a LEtr. Ces éléments ne permettent pas non plus de conclure que le refus de prolonger l'autorisation du recourant serait disproportionné.
4.
Compte tenu de ce qui précède, le recours doit être rejeté, avec suite de frais à la charge du recourant (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1.
Le recours est rejeté.
2.
Les frais judiciaires, arrêtés à 2'000 fr., sont mis à la charge du recourant.
3.
Le présent arrêt est communiqué au mandataire du recourant, au Service des migrations et au Département de l'économie du canton de Neuchâtel, au Tribunal cantonal de la République et canton de Neuchâtel, ainsi qu'à l'Office fédéral des migrations.
Lausanne, le 17 février 2014
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: Zünd
La Greffière: Rochat