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 Art. 114 lit. c ZPO ü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.