Sachverhalt: A. X._ (Kläger, Beschwerdeführer) arbeitete seit Oktober 1988 als nebenamtlicher Fachlehrer für Rechtslehren/HTL für das "Institut A._". Der Schulbetrieb wurde in der Folge wiederholt auf neue Rechtsträger übertragen. Zuletzt war die "Stiftung B._" (ab dem 13. Juli 2012 unter dem neuen Namen "Y._" [Beklagte, Beschwerdegegnerin]) bis am 31. Dezember 2011 Rechtsträgerin der damaligen Ingenieurschule. Per 1. Januar 2012 sollte der privatrechtliche Schulbetrieb der B._ der "Y._" angegliedert werden. In einem gemeinsam verfassten Schreiben der B._ und der Y._ vom 9. Mai 2011 wurde dem Kläger mitgeteilt, dass er mit seinem Lehrpensum von weniger als 20 % der Personenkategorie "Einzelentschädiger" zugeteilt worden sei und dass die Angehörigen dieser Kategorie im Juni/August 2011 schriftlich über ihren künftigen Einsatz informiert würden. Mit Schreiben vom 11. Mai 2011 kündigte die B._ dem Kläger das Arbeitsverhältnis per 15. August 2011. Im Zeitpunkt der Kündigung war der Kläger 70-jährig. B. Am 20. Juni 2012 reichte der Kläger beim Arbeitsgericht Zürich eine Forderungsklage gegen die Beklagte ein, mit dem Begehren, die Beklagte sei zu verurteilen, ihm Fr. 25'074.-- (9 Monatslöhne brutto) zuzüglich Zins ab 15. Februar 2012 (6 Monatslöhne) bzw. ab 31. Mai 2012 (3 Monatslöhne) zu bezahlen. Dabei hielt der Kläger den Anspruch auf Abgangsentschädigung aus langjährigem Arbeitsverhältnis ausdrücklich vor. Das Arbeitsgericht wies die Klage mit Urteil vom 24. April 2013 ab. Gegen dieses Urteil erhob der Kläger Berufung an das Obergericht des Kantons Zürich, welches die Klage mit Urteil vom 25. Juni 2013 ebenfalls abwies. C. Mit Beschwerde in Zivilsachen beantragt der Kläger dem Bundesgericht, das Urteil des Obergerichts des Kantons Zürich vom 25. Juni 2013 sowie das Urteil des Bezirksgerichts Zürich (recte: Arbeitsgericht Zürich) vom 24. April 2013 seien aufzuheben und die Klage gutzuheissen. Die Beschwerdegegnerin beantragt die Abweisung der Beschwerde, die Vorinstanz hat auf eine Vernehmlassung verzichtet. Der Beschwerdeführer reichte unaufgefordert eine Replik ein. 