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. 