Sachverhalt:
A.
A._ (Kläger, Beschwerdeführer) war ab dem 14. September 2011 als Zugbegleiter (Güterverkehr) für die B._ AG (Beklagte, Beschwerdegegnerin) tätig. Am 26. April 2012 kündigte die Beklagte das Arbeitsverhältnis mit dem Kläger ordentlich per 31. Mai 2012. Gegen die Kündigung erhob der Kläger am 4. Mai 2012 Einsprache. Der Kläger stellte sich auf den Standpunkt, die Kündigung sei missbräuchlich, da sie aus rassistischen Motiven erfolgt bzw. er gemobbt worden sei.
B.
Am 30. September 2013 reichte der Kläger beim Arbeitsgericht Zürich Klage ein und forderte von der Beklagten nach zwei Anpassungen seiner Rechtsbegehren sinngemäss eine Entschädigung wegen missbräuchlicher Kündigung in der Höhe von Fr. 19'200.--, bestehend aus drei Bruttomonatslöhnen von Fr. 6'400.--, zuzüglich 5 % Zins seit 1. Juni 2012. Zudem sei festzustellen, dass der Betrag von Fr. 576.70 für Spesen in der Zwischenzeit von der Beklagten bezahlt worden sei. Schliesslich beantragte er eine Änderung des Arbeitszeugnisses.
Mit Beschluss des Arbeitsgerichts vom 14. Januar 2016 wurde das Verfahren bezüglich der Spesenforderung vollumfänglich und mit Bezug auf die verlangten Zeugniskorrekturen grösstenteils als gegenstandslos erledigt abgeschrieben, da die Beklagte die Klage in diesen Punkten anerkannt und eine Anpassung des Arbeitszeugnisses gemäss den Vorschlägen des Klägers - abgesehen von einer Anpassung des Schlusssatzes - vorgenommen hatte. Mit Urteil von gleichem Tag wies das Arbeitsgericht die " (Rest-) Forderungsklage" bezüglich der vom Kläger geforderten Entschädigung für eine missbräuchliche Kündigung (Dispositiv-Ziffer 1) wie auch die " (Rest-) Zeugnisänderungsklage" des Klägers (Dispositiv-Ziffer 2) ab. Da der Streitwert von Fr. 36'979.70 die Streitwertgrenze nach <ref-law> überstieg, war das Verfahren vor Arbeitsgericht kostenpflichtig. Das Arbeitsgericht auferlegte die Gerichtskosten von insgesamt Fr. 7'200.-- im Umfang von Fr. 6'1 56.-- dem Kläger und im Umfang von Fr. 1'044.-- der Beklagten, wobei der Anteil des Klägers zufolge Gewährung der unentgeltlichen Rechtspflege einstweilen auf die Gerichtskasse genommen wurde. Sodann wurde der Kläger verpflichtet, der Beklagten eine Parteientschädigung von Fr. 8'165.-- zu bezahlen.
Gegen das Urteil des Arbeitsgerichts erhob der Kläger Berufung an das Obergericht des Kantons Zürich. Das Obergericht entschied mit Beschluss vom 3. August 2016, dass vorgemerkt werde, dass die Dispositiv-Ziffer 2 [bezüglich der Zeugnisänderungsklage] des Urteils des Arbeitsgerichts rechtskräftig geworden sei. Sodann wies das Obergericht das Gesuch des Klägers um Gewährung der unentgeltlichen Rechtspflege und um Bestellung eines unentgeltlichen Rechtsbeistands für das Berufungsverfahren ab. Mit Urteil vom gleichen Tag wies das Obergericht sodann die " (Rest-) Forderungsklage" [bezüglich der Entschädigung für eine missbräuchliche Kündigung] des Klägers ab und bestätigte die erstinstanzlichen Kosten- und Entschädigungsfolgen.
C.
Dagegen erhob der Beschwerdeführer Beschwerde in Zivilsachen an das Bundesgericht und beantragt in seinem Hauptbegehren, in Aufhebung des Urteils des Obergerichts sei die Beschwerdegegnerin zu verurteilen, dem Beschwerdeführer als Entschädigung wegen missbräuchlicher Kündigung einen Betrag von Fr. 19'200.-- zuzüglich 5 % Zins seit 1. Juni 2012 zu bezahlen. Im Weiteren beantragt er in seinen ausführlichen Eventual- und Subeventualanträgen die Rückweisung der Streitsache an die Vorinstanz bzw. die Erstinstanz. Der Beschwerdeführer beantragt im Weiteren, die Ziffern 2 und 3 des Beschlusses des Obergerichts seien aufzuheben, und es sei das Gesuch des Beschwerdeführers um Gewährung der unentgeltlichen Rechtspflege für das Berufungsverfahren gutzuheissen und Rechtsanwalt Mark Sollberger als unentgeltlicher Rechtsbeistand zu bestellen. Alsdann seien die Ziffern 2, 4 und 5 des Urteils des Obergerichts aufzuheben und es seien sämtliche Verfahrenskosten der beiden Vorinstanzen der Beschwerdegegnerin aufzuerlegen und diese sei zu verpflichten, dem Beschwerdeführer die Parteikosten vor den beiden Vorinstanzen auf gerichtliche Bestimmung hin vollumfänglich zu ersetzen. Schliesslich sei ihm auch für das bundesgerichtliche Verfahren die unentgeltliche Rechtspflege zu gewähren und es sei ihm Rechtsanwalt Mark Sollberger als unentgeltlicher Rechtsbeistand beizuordnen.
Der Beschwerdeführer reichte am 5. Oktober 2016 eine weitere Eingabe bezüglich seiner finanziellen Situation ein.
Mit Präsidialverfügung vom 11. Oktober 2016 wurde der Beschwerde die aufschiebende Wirkung erteilt.
Es wurden keine Vernehmlassungen zur Beschwerde eingeholt.

Erwägungen:
1.
Die Sachurteilsvoraussetzungen sind erfüllt, insbesondere auch das Streitwerterfordernis von <ref-law> mit einem Streitwert von Fr. 19'200.--, und geben zu keinen Bemerkungen Anlass. Unter Vorbehalt einer rechtsgenüglichen Begründung (Art. 42 Abs. 2 und <ref-law>; vgl. Erwägung 2) ist daher auf die Beschwerde einzutreten.
2.
2.1. Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>). Mit Blick auf die allgemeinen Begründungsanforderungen an eine Beschwerde (Art. 42 Abs. 1 und 2 BGG) behandelt es aber grundsätzlich nur die geltend gemachten Rügen, sofern die rechtlichen Mängel nicht geradezu offensichtlich sind; es ist jedenfalls nicht gehalten, wie eine erstinstanzliche Behörde alle sich stellenden rechtlichen Fragen zu untersuchen, wenn diese vor Bundesgericht nicht mehr vorgetragen werden (<ref-ruling> E. 2 S. 88 f. mit Hinweisen). Unerlässlich ist im Hinblick auf Art. 42 Abs. 2 sowie <ref-law>, dass die Beschwerde auf die Begründung des angefochtenen Entscheids eingeht und im Einzelnen aufzeigt, worin eine Verletzung von Bundesrecht liegt. Die beschwerdeführende Partei soll in der Beschwerdeschrift nicht bloss die Rechtsstandpunkte, die sie im kantonalen Verfahren eingenommen hat, erneut bekräftigen, sondern mit ihrer Kritik an den als rechtsfehlerhaft erachteten Erwägungen der Vorinstanz ansetzen (<ref-ruling> E. 2 S. 89., 115 E. 2 S. 116). Die Begründung hat ferner in der Beschwerdeschrift selbst zu erfolgen und der blosse Verweis auf Ausführungen in anderen Rechtsschriften oder auf die Akten reicht nicht aus (<ref-ruling> E. 2 S. 116). Erfüllt eine Beschwerde diese Anforderungen nicht, ist darauf nicht einzutreten.
2.2. Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Dazu gehören sowohl die Feststellungen über den streitgegenständlichen Lebenssachverhalt als auch jene über den Ablauf des vor- und erstinstanzlichen Verfahrens, also die Feststellungen über den Prozesssachverhalt (<ref-ruling> E. 1.3.1 mit Hinweisen). Es kann die Sachverhaltsfeststellung der Vorinstanz nur berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law>). "Offensichtlich unrichtig" bedeutet dabei "willkürlich" (<ref-ruling> E. 2 S. 117; <ref-ruling> E. 1.5). Überdies muss die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein können (<ref-law>).
Für eine Kritik am festgestellten Sachverhalt gilt das strenge Rügeprinzip von <ref-law> (<ref-ruling> E. 2.3 S. 266 mit Hinweisen). Die Partei, welche die Sachverhaltsfeststellung der Vorinstanz anfechten will, muss klar und substanziiert aufzeigen, inwiefern diese Voraussetzungen erfüllt sein sollen (<ref-ruling> E. 1.3.1 S. 18 mit Hinweisen). Wenn sie den Sachverhalt ergänzen will, hat sie zudem mit präzisen Aktenhinweisen darzulegen, dass sie entsprechende rechtsrelevante Tatsachen und taugliche Beweismittel bereits bei den Vorinstanzen prozesskonform eingebracht hat (<ref-ruling> E. 2 S. 90). Genügt die Kritik diesen Anforderungen nicht, können Vorbringen mit Bezug auf einen Sachverhalt, der vom angefochtenen Entscheid abweicht, nicht berücksichtigt werden (<ref-ruling> E. 1.3.1 S. 18).
Diese Grundsätze verkennt der Beschwerdeführer, wenn er unter dem Titel "Sachverhalt- und Prozessgeschichte" bloss seine eigene Sicht der Dinge schildert, ohne dabei Sachverhaltsrügen nach den oben genannten Voraussetzungen zu erheben. Darauf kann nicht abgestellt werden.
3.
Die Vorinstanz erwog, Gegenstand des vorliegenden Berufungsverfahrens bilde die Frage, ob die Beschwerdegegnerin dem Beschwerdeführer infolge missbräuchlicher Kündigung eine Entschädigung schulde. Der Beschwerdeführer habe sich vor der Erstinstanz zur Begründung der Missbräuchlichkeit auf den Standpunkt gestellt, ihm sei infolge verschiedener rassistisch motivierter gegen ihn gerichteter Übergriffe gekündigt worden. Mit der E-Mail [von C._] vom 16. Januar 2012 sowie den Vorfällen vom 1. Februar 2012 und vom 25. April 2012, die der Beschwerdeführer im Wesentlichen zur Begründung des Rassismusvorwurfs ins Feld führte, habe sich die Erstinstanz im Detail auseinandergesetzt und erwogen, dass sich daraus keine schwerwiegenden, rassistisch motivierten Übergriffe gegen den Beschwerdeführer ableiten liessen. Die entsprechenden Erwägungen der Erstinstanz beanstande der Beschwerdeführer nicht. So nehme er in seiner Berufungsschrift kaum Bezug auf den erstinstanzlichen Entscheid bzw. lasse kaum Schlüsse zu, was im Einzelnen konkret angefochten werde und inwiefern die Erwägungen der Erstinstanz unzutreffend sein sollten. Der Beschwerdeführer setze sich mit den entscheidrelevanten Erwägungen der Vorinstanz nur ungenügend auseinander. Immerhin könne der Berufungsschrift im Wesentlichen entnommen werden, dass der Beschwerdeführer neu offenbar davon ausgehe, die beiden Zugführer C._ und D._ hätten gegen ihn eine "Neid-Mobbing-Kampagne" bzw. eine "Berufsunfähigkeit-Mobbing-Kampagne" geführt.
Die Vorinstanz erwog bezüglich dieser Mobbing-Kampagne zusammenfassend, dass der vom Beschwerdeführer behaupteten Mobbing-Kampagne "schlicht das Tatsachenfundament" fehle. Es sei der Beschwerdegegnerin daher letztlich zuzustimmen, wenn sie in der Berufungsantwort zum Schluss komme, dem Beschwerdeführer sei es vor der Erstinstanz nicht gelungen, auch nur einen einzigen Bezug zwischen seiner Hautfarbe und den Handlungen der Beschwerdegegnerin aufzuzeigen, weshalb er nun versuche, vor oberer Instanz seine Argumentation neu auszurichten und das Schwergewicht der Argumentation auf das Mobbing zu legen. Vom Beschwerdeführer werde ausserdem in seiner Berufungsschrift in keiner Weise dargetan, so die Vorinstanz weiter, inwiefern das von ihm behauptete Mobbing durch die beiden Zugführer D._ und C._ für die Kündigung der Beschwerdegegnerin überhaupt kausal gewesen sein sollte. Dass sich das Verhalten seiner Arbeitskollegen beispielsweise negativ auf seine Leistungen aufgewirkt hätte, so dass ihm die Beschwerdegegnerin infolgedessen gekündigt hätte, behaupte er jedenfalls gerade nicht. Insgesamt sei daher mit der Erstinstanz festzustellen, dass dem Beschwerdeführer der Nachweis eines missbräuchlichen Kündigungsgrundes bzw. missbräuchlicher Kündigungsumstände nicht gelungen sei.
4.
4.1. Wenn der Beschwerdeführer vor Bundesgericht das Beweisverfahren vor der Erstinstanz kritisiert, kann darauf von vornherein nicht eingetreten werden, da die Beschwerde an das Bundesgericht nur gegen Entscheide letzter kantonaler Instanzen zulässig ist (<ref-law>).
4.2.
4.2.1. Soweit der Beschwerdeführer der Vorinstanz eine Verletzung seines Beweisführungsanspruchs bzw. der "Konzentrationsmaxime" bezüglich der von ihm beantragten Zeugenbefragungen des E._-Personals oder seiner weiteren gestellten Fragen bezüglich anderer Zeugen vorwirft, die Vorinstanz kritisiert, da sie das "Beweisthema zu eng gefasst" und sie irrtümlich erwogen habe, er habe die Fakten bezüglich dem Mobbing nicht rechtzeitig vorgebracht, und er schliesslich behauptet, den "negativen Beweis" bezüglich den von der Beschwerdegegnerin vorgebrachten Kündigungsgründe erbracht sowie die von ihm behauptete "Mobbing-Kampagne" nachgewiesen zu haben, genügt der Beschwerdeführer den vorgenannten Begründungsanforderungen an eine Beschwerde an das Bundesgericht nicht (vgl. Erwägung 2.1). Er geht bezüglich dieser Rügen grösstenteils überhaupt nicht und im Weiteren zumindest nicht hinreichend auf die einzelnen Erwägungen der Vorinstanz ein. Vielmehr trägt er in seiner Beschwerdeschrift bloss nochmals sämtliche Vorbringen aus dem kantonalen Verfahren vor und unterbreitet dem Bundesgericht den Fall wie bei einer ersten Instanz zur Beurteilung. So beispielsweise wenn der Beschwerdeführer ausführt, dass die "Mobbing-Kampagne (...) aufgrund nachfolgender Beweismittel als mit überwiegender Wahrscheinlichkeit erstellt" gelte und anschliessend auf vier Seiten nochmals seine Behauptungen und Beweismittel, die er im kantonalen Verfahren vorbrachte, im Einzelnen aufzählt, ohne dabei auf die Erwägungen der Vorinstanz bezüglich der "Mobbing-Kampagne" auch nur mit einem Wort einzugehen. Damit genügt er den Begründungsanforderungen an eine Beschwerde an das Bundesgericht nicht. Vielmehr wäre in der Beschwerdeschrift an den als rechtsfehlerhaft erachteten Erwägungen der Vorinstanz zur "Mobbing-Kampagne" (Erwägungen 5.1 - 5.4 S. 15 - 18 im angefochtenen Entscheid) anzusetzen, auf die diesbezügliche Begründung der Vorinstanz hinreichend einzugehen und im Einzelnen aufzuzeigen, worin eine Verletzung von Bundesrecht liegt.
Vor diesem Hintergrund erweist sich die Beschwerde der oben genannten Rügen des Beschwerdeführers als nicht hinreichend begründet, weshalb darauf nicht einzutreten ist.
4.3.
4.3.1. Der Beschwerdeführer rügt im Zusammenhang mit dem von ihm behaupteten Mobbingvorwurf, dass die "Konzentrationsmaxime" nur für "Fakten und Beweismittel" gelte, nicht aber für "rechtliche Qualifikationen und Subsumptionen". Ob die geltend gemachten und nachgewiesenen Fakten in ihrer Gesamtheit rechtlich als Mobbing zu qualifizieren seien oder nicht, sei eine Rechtsfrage und unterliege daher nicht der "Konzentrationsmaxime". Er habe daher ohne Weiteres diesbezüglich auch im Schlussplädoyer vor der Erstinstanz und später vor Vorinstanz weitere Ausführungen machen können, ohne damit in irgendeiner Weise die Konzentrationsmaxime, die nur für die "reinen Fakten und Beweismittel" gelte, zu verletzen.
Mit diesen Ausführungen möchte der Beschwerdeführer wohl sinngemäss rügen, dass die Vorinstanz seine neue rechtliche Argumention bezüglich der "Mobbing-Kampagne" zu Unrecht aus dem Recht gewiesen und damit <ref-law> falsch angewandt habe.
Diese Rüge beruht auf einem falschen Verständnis des angefochtenen Entscheids: Die Vorinstanz erwog, dass soweit der Beschwerdeführer in seiner Berufungsschrift neu "immer und immer wieder" von einer sogenannten Mobbing-Kampagne spreche, mache er sinngemäss geltend, es liege eine Art qualifiziertes Mobbing vor. Die Darstellung des Beschwerdeführers vor Obergericht, es habe sich quasi um eine von D._ und C._ gemeinsam angeführte, gegen ihn gerichtete Aktion gehandelt, sei dabei neu, habe er doch vor der Erstinstanz nie von einer solchen Kampagne gesprochen. Entschuldigungsgründe im Sinne von <ref-law> für das verspätete Vorbringen wurden vom Beschwerdeführer nicht weiter dargetan. Die diesbezüglichen neuen Tatsachenbehauptungen des Beschwerdeführers seien daher unbeachtlich.
Die Vorinstanz wies damit die vom Beschwerdeführer vorgebrachten neuen Tatsachenbehauptungen im Zusammenhang mit der Mobbing-Kampagne aus dem Recht und nicht seine neue rechtliche Argumentation, wie er irrtümlich behauptet. Seine diesbezügliche Rüge geht damit fehl.
4.3.2. Sodann behauptet der Beschwerdeführer eine Verletzung "verschiedener Schutz- und Fürsorgepflichten" nach <ref-law>. Die Beschwerdegegnerin habe von ihm behauptete Vorwürfe und Beanstandungen "in keiner Weise" abgeklärt und die Verantwortlichen der Beschwerdegegnerin hätten "rein gar nichts unternommen". Er stützt sich dabei einzig auf tatsächliche Elemente, die im vorinstanzlich festgestellten Sachverhalt nicht festgestellt wurden, ohne hinreichende Sachverhaltsrügen nach den oben erwähnten Grundsätzen zu erheben (Erwägung 2.2). Darauf kann nicht abgestellt werden.
Dass die Vorinstanz gestützt auf den festgestellten Sachverhalt <ref-law> verletzt hätte, legt der Beschwerdeführer nicht dar, sodass dies nicht beurteilt zu werden braucht.
4.4. Es gelingt dem Beschwerdeführer damit nicht aufzuzeigen, dass die Vorinstanz Bundesrecht verletzte, als sie zum Schluss kam, dass es dem Beschwerdeführer nicht gelungen sei, eine missbräuchliche Kündigung nachzuweisen. Da es daher bereits an einer missbräuchlichen Kündigung fehlt, muss auf die Frage bzw. die Berechnung einer Entschädigung nach <ref-law> und die entsprechenden Rügen des Beschwerdeführers nicht eingegangen werden.
5.
5.1. Der Beschwerdeführer bringt vor, entgegen der Auffassung der Vorinstanz könne sein Rechtsbegehren auf Entschädigung aus missbräuchlicher Kündigung nicht als aussichtslos betrachtet werden, weshalb ihm die unentgeltliche Rechtspflege für das Berufungsverfahren zu gewähren sei.
Als Grund für die Verweigerung der Gewährung der unentgeltlichen Rechtspflege und der Bestellung eines unentgeltlichen Rechtsbeistands für das kantonale Berufungsverfahren gab die Vorinstanz an, die Berufung des Beschwerdeführers habe sich als aussichtslos erwiesen. Dem hält der Beschwerdeführer nichts entgegen, was über seine - verworfene (Erwägung 4) - Ansicht hinausginge, seine Berufung hätte gutgeheissen werden müssen, da die Kündigung vom 26. April 2012 missbräuchlich sei bzw. dass sein "Recht auf Beweis" und sein Anspruch auf rechtlichen Gehörs verletzt worden sei. Es hat damit sein Bewenden.
5.2. Schliesslich beantragt der Beschwerdeführer eine andere Verteilung der Prozesskosten für die kantonalen Verfahren. Er begründet dies aber nur für den Fall der Gutheissung seiner Beschwerde. Da die Beschwerde nach dem Gesagten nicht gutgeheissen werden kann, erübrigt sich auch eine andere Verlegung der Prozesskosten.
6.
Nach dem Gesagten ist die Beschwerde abzuweisen, soweit auf sie eingetreten werden kann. Weil die Beschwerde nach dem Ausgeführten als von vornherein aussichtslos erscheint, ist das Gesuch um Gewährung der unentgeltlichen Rechtspflege bzw. Bestellung eines unentgeltlichen Rechtsbeistands für das bundesgerichtliche Verfahren abzuweisen (<ref-law>), wobei darüber unter den gegebenen Umständen nicht vorgängig separat entschieden werden musste (vgl. Urteil 4A_20/2011 vom 11. April 2011 E. 7.2.2).
Dem Ausgang des Verfahrens entsprechend wird der Beschwerdeführer kostenpflichtig (<ref-law>). Der Beschwerdegegnerin, die sich nur zum Gesuch um aufschiebende Wirkung zu äussern hatte und auf eine Vernehmlassung hierzu verzichtete, ist aus dem bundesgerichtlichen Verfahren kein entschädigungspflichtiger Aufwand erwachsen, weshalb ihr keine Parteientschädigung zuzusprechen ist (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Das Gesuch des Beschwerdeführers um Bewilligung der unentgeltlichen Rechtspflege für das bundesgerichtliche Verfahren wird abgewiesen.
3.
Die Gerichtskosten von Fr. 1'000.-- werden dem Beschwerdeführer auferlegt.
4.
Es wird keine Parteientschädigung zugesprochen.
5.
Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, I. Zivilkammer, schriftlich mitgeteilt.
Lausanne, 7. November 2016
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Kiss
Der Gerichtsschreiber: Brugger