Faits :
A.
X._, ressortissant tunisien né en 1973, est entré en Suisse en mars 2001 pour y étudier. Le 13 janvier 2009, son autorisation de séjour pour études n'a pas été renouvelée et son renvoi de Suisse a été prononcé. Le 7 juillet 2009, l'intéressé a épousé une ressortissante suisse née en 1981. Il a été mis au bénéfice d'une autorisation de séjour au titre du regroupement familial. Le 4 mars 2010, le couple a eu une fille. Il s'est séparé en 2011.
B.
Par décision du 10 avril 2014, le Service des migrations de la République et canton de Neuchâtel a prolongé l'autorisation de séjour de X._, sous réserve de l'approbation de l'Office fédéral des migrations (actuellement le Secrétariat d'Etat aux migrations). Le 29 juillet 2014, celui-ci a refusé d'approuver la prolongation de l'autorisation de séjour en faveur de X._ et a prononcé son renvoi de Suisse. L'intéressé a contesté ce prononcé auprès du Tribunal administratif fédéral par acte du 25 août 2014.
Par arrêt du 17 février 2016, le Tribunal administratif fédéral a rejeté le recours. Il a jugé en bref que X._ ne disposait ni de l'autorité parentale, ni du droit de garde sur sa fille. S'il semblait certes entretenir un lien affectif particulièrement fort avec celle-ci, il n'entretenait cependant pas de lien économique. De plus, sa situation financière était obérée et il dépendait durablement de l'aide sociale. Il a ainsi exclu toute raison personnelle majeure qui aurait imposé la poursuite du séjour en Suisse.
C.
Agissant par la voie du recours en matière de droit public, X._ demande au Tribunal fédéral, sous suite de frais et dépens, outre l'effet suspensif et l'assistance judiciaire, d'annuler l'arrêt du Tribunal administratif fédéral du 17 février 2016 et de prolonger son autorisation de séjour; subsidiairement de renvoyer la cause au Tribunal administratif fédéral pour nouvelle décision dans le sens des considérants. Outre un établissement inexact des faits, il se plaint de violation du droit fédéral et international.
Par ordonnance du 18 avril 2016, le Président de la IIe Cour de droit public du Tribunal fédéral a admis la demande d'effet suspensif.
Le Tribunal administratif fédéral renonce à prendre position. Le Secrétariat d'Etat aux migrations conclut au rejet du recours. Dans des observations finales, X._ a confirmé ses conclusions.

Considérant en droit :
1.
1.1. D'après l'art. 83 let. c ch. 2 LTF, le recours en matière de droit public est irrecevable à l'encontre des 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. Il suffit toutefois qu'il existe un droit potentiel à l'autorisation, étayé par une motivation soutenable, pour que cette clause d'exclusion ne s'applique pas et que, partant, la voie du recours en matière de droit public soit ouverte. La question de savoir si les conditions d'un tel droit sont effectivement réunies relève du fond (<ref-ruling> consid. 1.1 p. 179 s.). En l'occurrence, du moment que le recourant vit séparé d'une ressortissante suisse avec laquelle il a eu un enfant, les art. 50 al. 1 LEtr (RS 142.20) et 8 CEDH sont potentiellement de nature à lui conférer un droit à une autorisation de séjour, de sorte que la voie du recours en matière de droit public est ouverte.
1.2. Pour le surplus, l'arrêt attaqué est une décision finale (<ref-law>), rendue par le Tribunal administratif fédéral (<ref-law>) dans une cause de droit public (<ref-law>). Le recours ayant de surcroît été déposé en temps utile (<ref-law>) et dans les formes requises (<ref-law>), par le recourant qui est atteint par la décision entreprise et a un intérêt digne de protection à son annulation ou à sa modification, de sorte qu'il faut lui reconnaître la qualité pour recourir (<ref-law>), il est partant recevable.
2.
Citant à tort l'<ref-law> (à la place de l'<ref-law>), le recourant invoque en premier lieu un établissement inexact des faits.
2.1. Le Tribunal fédéral statue sur la base des faits établis par l'autorité précédente (cf. <ref-law>). Le recours ne peut critiquer les constatations de fait que si les faits ont été établis de façon manifestement inexacte ou en violation du droit au sens de l'<ref-law>, et si la correction du vice est susceptible d'influer sur le sort de la cause (<ref-law>), ce que la partie recourante doit démontrer d'une manière circonstanciée, conformément aux exigences de motivation de l'<ref-law> (cf. <ref-ruling> consid. 1.4.3 p. 254 s.). La notion de "manifestement inexacte" correspond à celle d'arbitraire au sens de l'art. 9 Cst. (<ref-ruling> consid. 2.1 p. 450). En particulier, le Tribunal fédéral n'entre pas en matière sur des critiques de type appellatoire portant sur l'état de fait ou sur l'appréciation des preuves (<ref-ruling> consid. 5.1 p. 356).
2.2. Le recourant conteste l'établissement des faits sous plusieurs points.
Il mentionne tout d'abord que c'est à tort que l'autorité précédente a retenu qu'il ne bénéficiait pas de l'autorité parentale conjointe sur sa fille. Selon lui, lorsqu'une procédure de divorce est en cours, l'autorité parentale n'est pas prononcée de manière définitive et, en application de l'<ref-law>, celle-ci est de toute façon conjointe. Or en l'espèce, c'est de manière purement appellatoire qu'il présente ses vision et appréciation des faits et les oppose à celles de l'autorité précédente. On ajoutera que contrairement à ce qu'il avance, durant une procédure de divorce ou une procédure de protection de l'union conjugale, si le bien de l'enfant le commande, le juge confie à l'un des parents l'autorité parentale exclusive (<ref-law>). La motivation du recourant quant à l'établissement inexacte des faits ne remplit par conséquent pas non plus les conditions de l'<ref-law>.
Le recourant conteste ensuite l'appréciation faite par l'autorité précédente d'une promesse d'embauche datée du 18 juin 2014. Selon ce courrier, le signataire est " éventuellement disposé à engager " le recourant dès l'obtention d'une autorisation de séjour. Compte tenu de cette formulation, il n'est pour le moins pas arbitraire de n'accorder qu'une force probante réduite à cet écrit, comme l'a fait le Tribunal administratif fédéral. De plus, comme on le verra ci-après, ce courrier, même s'il devait être considéré comme probant, n'a aucune incidence sur l'issue de la cause.
Finalement, le recourant conteste l'appréciation du Secrétariat d'Etat voulant qu'il ne s'investisse pas à suffisance pour contribuer à l'entretien de sa famille. Or, en tant que le recourant dirige son grief d'établissement inexact des faits directement contre la décision du Secrétariat d'Etat, celui-ci doit d'emblée être écarté. Il ne saurait en effet se plaindre d'un tel établissement dans le présent recours dirigé contre l'arrêt ultérieur du Tribunal administratif fédéral, la saisine de ce dernier ayant un effet dévolutif entraînant le dessaisissement de l'instance précédente (cf. arrêt 2C_312/2011 du 26 juillet 2011 consid. 4).
2.3. Compte tenu de ce qui précède, c'est sans arbitraire que le Tribunal administratif fédéral a établi les faits. Le grief d'établissement inexact des faits soulevé par le recourant doit par conséquent être écarté.
3.
3.1. Aux termes de l'art. 42 al. 1 LEtr, le conjoint d'un ressortissant suisse ainsi que ses enfants célibataires de moins de 18 ans ont droit à l'octroi d'une autorisation de séjour et à la prolongation de sa durée de validité à condition de vivre en ménage commun avec lui. En l'espèce, le recourant vit séparé d'une ressortissante suisse. Il ne peut se prévaloir de l'art. 42 LEtr.
3.2. Selon l'art. 50 al. 1 let. a LEtr, après dissolution de la famille, le droit du conjoint et des enfants à 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 l'intégration est réussie. La période minimale de trois ans de l'union conjugale commence à courir dès le début de la cohabitation effective des époux en Suisse et s'achève au moment où ceux-ci cessent de faire ménage commun. Seules les années de mariage et non de concubinage sont pertinentes (<ref-ruling> consid. 4.1 p. 348). En l'espèce, le recourant s'est marié le 7 juillet 2009 avec une ressortissante suisse et s'est séparé de celle-ci en 2011, si bien que son union conjugale a duré moins de trois ans. Partant, il ne peut se prévaloir de l'art. 50 al. 1 let. a LEtr. La condition de l'intégration réussie étant cumulative avec celle de la durée de l'union conjugale (<ref-ruling> consid. 4 p. 347 s.), les explications du recourant à ce propos sont sans pertinence.
4.
Il convient par conséquent d'examiner dans quelle mesure la poursuite du séjour du recourant en Suisse s'impose pour des raisons personnelles majeures au sens de l'art. 50 al. 1 let. b LEtr.
4.1. Selon l'art. 50 al. 1 let. b LEtr, après dissolution de la famille, le droit du conjoint et des enfants à 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 lorsque la poursuite du séjour du recourant en Suisse s'impose pour des raisons personnelles majeures. De telles raisons peuvent en particulier découler d'une relation digne de protection avec un enfant qui a le droit de séjourner en Suisse (cf. <ref-ruling> consid. 2.1 p. 318 s.). Dans ce cas, les conditions posées par l'art. 50 al. 1 let. b LEtr ne recoupent pas nécessairement celles de l'octroi d'un titre de séjour fondé sur l'art. 8 CEDH. Le droit au respect de la vie familiale garantie par les art. 8 CEDH et 13 Cst. doit néanmoins être pris en compte dans l'application de l'art. 50 al. 1 let. b LEtr dont l'application ne saurait être plus restrictive que celle des art. 8 CEDH et 13 Cst. (arrêt 2C_652/2013 du 17 décembre 2013 consid. 2.3 et les références citées, non publié in <ref-ruling>).
4.2. Le parent qui n'a pas l'autorité parentale ni la garde de l'enfant ne peut d'emblée entretenir une relation familiale avec celui-ci que de manière limitée, en exerçant le droit de visite dont il bénéficie. Or, il n'est en principe pas nécessaire que, dans l'optique de pouvoir exercer son droit de visite, le parent étranger soit habilité à résider durablement dans le même pays que son enfant. Sous l'angle du droit à une vie familiale (cf. art. 8 par. 1 CEDH et art. 13 al. 1 Cst.), il suffit en règle générale que le parent vivant à l'étranger exerce son droit de visite dans le cadre de séjours de courte durée, au besoin en aménageant ses modalités quant à la fréquence et à la durée (cf. <ref-ruling> consid. 2.2 p. 319). Le droit de visite d'un parent sur son enfant ne doit en effet pas nécessairement s'exercer à un rythme bimensuel et peut également être organisé de manière à être compatible avec des séjours dans des pays différents (cf. arrêt 2C_1031/2011 du 22 mars 2012 consid. 4.2.3). Selon la jurisprudence constante du Tribunal fédéral, un droit plus étendu ne peut le cas échéant exister qu'en présence de liens familiaux particulièrement forts d'un point de vue affectif et économique, lorsque cette relation ne pourrait pratiquement pas être maintenue en raison de la distance qui sépare le pays de résidence de l'enfant du pays d'origine de son parent, et que l'étranger a fait preuve en Suisse d'un comportement irréprochable (cf. <ref-ruling> consid. 2.2 p. 319 et les arrêts cités).
4.3. Il ressort de l'arrêt entrepris que le recourant ne bénéficie ni de l'autorité parentale, ni du droit de garde sur sa fille. Par contre, le Tribunal administratif fédéral a considéré qu'au vu du droit de visite exercé en dernier lieu par le recourant sur son enfant, c'est-à-dire, depuis fin avril 2013, un week-end sur deux et la moitié des vacances scolaires et, depuis septembre 2013, le plus largement possible, le recourant semble entretenir un lien affectif particulièrement fort avec sa fille. Dans ces circonstances, au vu de la jurisprudence relative au droit de visite usuel (cf. arrêt 2C_420/2015 du 1 er octobre 2015 consid. 2.3 et les références citées), et malgré un droit de visite plutôt chaotique les années précédentes (notamment un droit de visite exercé dans un Point Rencontre), on doit retenir, avec l'autorité précédente, que le lien affectif avec l'enfant est actuellement particulièrement fort.
4.4. Quant à l'aspect économique, il ressort de l'arrêt entrepris que le recourant, qui bénéficie d'une maîtrise en marketing et d'une certaine expérience professionnelle en Tunisie, n'a jamais payé de pension alimentaire en faveur de sa fille. Il est cependant constaté que la pension alimentaire à laquelle le recourant a été astreint n'a jamais été exigible. Le juge civil a en effet ratifié une convention intervenue entre les époux, selon laquelle le recourant doit s'acquitter d'une pension alimentaire mensuelle de 500 fr. en faveur de sa fille, dès qu'il aura terminé sa formation et trouvé du travail. Or, le recourant ne travaille pas. Dans ces conditions, l'autorité précédente a jugé que si aucun paiement n'avait pu être exigé, il fallait tout de même mentionner que le recourant avait préféré poursuivre ses études plutôt que de participer à l'entretien de la famille. Elle a également relevé que le recourant avait effectué plusieurs recherches d'emploi, mais que le dossier ne comportait que peu de réponses écrites de potentiels employeurs et que seul un faible nombre des recherches indiquées sur les formulaires étaient assorties d'un tampon des employeurs contactés. Avec une dizaine de postulations en 2014, le Tribunal administratif fédéral reproche au recourant de ne pas avoir effectué un nombre suffisant de recherches et de ne pas avoir été en mesure d'obtenir, en six ans, un travail salarié stable lui permettant de percevoir un revenu pour créer un quelconque lien économique avec sa fille.
Le recourant estime avoir du mal à trouver un emploi en raison de son statut en Suisse et du fait que, depuis 2014, il attend une décision quant à son autorisation de séjour. Certes, depuis que le Secrétariat d'Etat aux migrations a refusé d'approuver la prolongation de l'autorisation de séjour du recourant le 29 juillet 2014, la recherche d'un emploi stable s'est éventuellement compliquée. Il ne faut cependant pas perdre de vue que depuis l'obtention de son autorisation de séjour en 2009, le recourant n'a jamais pratiqué d'activité professionnelle qui lui aurait permis de subvenir à ses besoins et à ceux de sa famille, ce malgré sa formation. Même entre la fin de ses études en 2012 et la décision du Secrétariat d'Etat aux migrations en 2014, le recourant n'a pas démontré un grand intérêt à mettre en place une situation professionnelle stable, comme l'a retenu le Tribunal administratif fédéral de manière à lier le Tribunal fédéral (cf. consid. 2.1 ci-dessus). Or, la séparation de son couple et son obligation d'entretien envers sa fille auraient dû le conduire à chercher activement un emploi. Dans ces conditions, il ne saurait être considéré, comme le recourant semble vouloir le faire croire, qu'il avait la volonté de subvenir aux besoins de son enfant, mais sans le pouvoir. L'arrêt du Tribunal administratif fédéral doit donc être confirmé en tant qu'il constate l'absence de lien économique fort entre le recourant et son enfant.
4.5. Finalement, si le recourant présente un casier judiciaire vierge et qu'il n'est pas aux poursuites, il faut tout de même relever qu'en mars 2014, sa dette d'aide sociale s'élevait à 60'000 fr. De plus, il n'est pas exclu que ce montant ait encore augmenté depuis lors, le recourant n'ayant pas donné suite à l'ordonnance de l'autorité précédente lui demandant de produire un décompte actualisé de cette dette. Sur le vu de la situation professionnelle du recourant (cf. consid. 4.4 ci-dessus), il faut retenir, à l'instar du Tribunal administratif fédéral, que rien ne laisse présager que le recourant arrivera à atteindre, dans un proche avenir, l'autonomie financière suffisante pour subvenir lui-même à ses besoins. Celui-ci devra donc être soutenu de manière durable par l'aide sociale, comme c'est le cas depuis 2011 déjà. Le fait qu'il ne " représente pas un risque pour la sécurité nationale ni pour la sûreté publique ou pour la défense de l'ordre et la prévention des infractions pénales " n'est pas pertinent en l'espèce. Le simple respect de l'ordre et de la sécurité publique en droit des étrangers ne se recoupe pas nécessairement avec la violation de dispositions pénales, de sorte que l'appréciation émise par l'autorité de police des étrangers peut s'avérer plus rigoureuse que celle de l'autorité pénale (cf. <ref-ruling> consid. 4.3 p. 150 s. et les références citées).
4.6. S'agissant finalement de la réintégration sociale dans le pays de provenance, l'art. 50 al. 2 LEtr exige qu'elle semble fortement compromise (<ref-ruling> consid. 5.3 p. 4). La question n'est donc pas de savoir s'il est plus facile pour la personne concernée de vivre en Suisse, mais uniquement d'examiner si, en cas de retour dans le pays d'origine, les conditions de la réintégration sociale, au regard de la situation personnelle, professionnelle et familiale de l'étranger, seraient gravement compromises (cf. <ref-ruling> consid. 3.1 p. 231 s.).
En l'occurrence, le Tribunal administratif fédéral a notamment relevé à juste titre que le recourant avait passé toute son enfance et son adolescence dans son pays d'origine. Le recourant ne démontre nullement qu'il pourrait se trouver dans une situation présentant des difficultés de réadaptation insurmontables en cas de retour en Tunisie. En outre, il bénéficie d'une formation en marketing obtenue dans une université tunisienne et d'une autre en gestion d'entreprise obtenue durant son séjour en Suisse qui lui permettront de se réintégrer professionnellement dans son pays d'origine. Compte tenu de ces éléments, l'autorité précédente pouvait retenir que la réintégration du recourant dans son pays d'origine ne serait pas fortement compromise.
Comme le fait valoir le recourant en citant la jurisprudence du Tribunal fédéral, la Tunisie, au même titre que le Maroc, est à une importante distance de la Suisse (cf. arrêt 2C_318/2013 du 5 septembre 2013 consid. 3.4.2). Toutefois, au contraire de la situation jugée par le Tribunal fédéral dans l'arrêt précité, le recourant ne présente pas de lien économique particulièrement fort avec son enfant et ne bénéficie pas d'une situation professionnelle stable ainsi que d'une autonomie financière. Dans ces conditions, la distance existant entre la Suisse et son pays d'origine ne revêt pas une importance à ce point particulière qu'elle s'opposerait au refus d'un titre de séjour en Suisse. Au demeurant, rien n'empêche le recourant d'exercer son droit de visite sur sa fille en venant la voir en Suisse lors de vacances ou, plus tard, en l'invitant à se rendre en Tunisie.
4.7. Le recourant ne présentant pas de lien économique fort avec son enfant, son comportement n'étant pas irréprochable et son retour en Tunisie n'étant pas gravement compromis, il ne saurait être question de violation de l'art. 50 al. 1 let. b LEtr et de l'art. 8 CEDH.
5.
En dernier lieu, hormis le lien du recourant avec sa fille, dont on a vu qu'il ne justifie pas à lui seul son séjour en Suisse, l'arrêt attaqué ne révèle aucun élément déterminant qui ferait apparaître le refus d'approuver la prolongation de l'autorisation de séjour du recourant comme disproportionné (cf. art. 96 LEtr). En tenant compte de l'âge d'arrivée en Suisse du recourant, de la durée et de la qualité de son séjour en Suisse, du fait que son intégration professionnelle et socioculturelle en Suisse n'est pas particulièrement marquée, des conséquences pour lui et son enfant d'un refus de demeurer en Suisse, de la possibilité de conserver des liens avec sa fille en dépit de l'éloignement et des possibilités d'intégration à l'étranger, c'est à bon droit que le Tribunal administratif fédéral a confirmé la proportionnalité du refus d'approuver la prolongation de l'autorisation de séjour du recourant.
6.
Les considérants qui précèdent conduisent au rejet du recours. Le recours étant d'emblée dénué de chances de succès, la requête d'assistance judiciaire est rejetée (<ref-law>). Les frais judiciaires sont mis à la charge du recourant (<ref-law>). Il n'est pas alloué de dépens (art. 68 al. 1 et 3 LTF).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est rejeté.
2.
La demande d'assistance judiciaire est rejetée.
3.
Les frais judiciaires, arrêtés à 1'000 fr., sont mis à la charge du recourant.
4.
Le présent arrêt est communiqué au mandataire du recourant, au Secrétariat d'Etat aux migrations, au Tribunal administratif fédéral, Cour III et au Service des migrations de la République et canton de Neuchâtel.
Lausanne, le 14 novembre 2016
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président : Seiler
Le Greffier : Tissot-Daguette