Sachverhalt:
A.
A.a. X._ (Arbeitnehmer, Kläger, Beschwerdeführer) war seit 1998 bei der Y._ AG (Arbeitgeberin, Beklagte, Beschwerdegegnerin) als Produktionsmitarbeiter angestellt. Ab dem 18. Oktober 2011 war der Arbeitnehmer von Dr. A._ immer wieder für unterschiedlich lange Zeit zu 100 % arbeitsunfähig geschrieben, so vom 18. Oktober bis 6. November 2011, vom 9. November bis 4. Dezember 2011 und vom 25. Januar bis 5. Februar 2012.
A.b. Am 16. Februar 2012 wurde der Arbeitnehmer vom Produktionsleiter der Arbeitgeberin aufgefordert, für einen dringend fertig zu stellenden Auftrag Mehrarbeit zu leisten. Der Arbeitnehmer verweigerte die Mehrarbeit, da er nach eigenen Angaben eigentlich gar nicht arbeitsfähig gewesen sei und sich selbst für die Leistung von 100 % "durchgebissen" habe. Es kam zu einem Wortwechsel zwischen dem Arbeitnehmer und dem Produktionsleiter bzw. dem Geschäftsführer der Arbeitgeberin, woraufhin dem Arbeitnehmer die Kündigung ausgehändigt wurde. Ein ärztliches Attest, welches die Arbeitsunfähigkeit des Arbeitnehmers am 16. Februar 2012 bescheinigt hätte, lag nicht vor. Der Arbeitnehmer macht geltend, die gegen ihn ausgesprochene Kündigung sei missbräuchlich.
B.
B.a. Mit Klage vom 19. Juni 2012 beantragte der Arbeitnehmer dem Kantonsgericht von Appenzell Ausserrhoden, die Arbeitgeberin sei zu verpflichten, ihm den Betrag von Fr. 15'762.50 nebst Zins zu bezahlen und es sei vom Nachklagerecht Vormerk zu nehmen. Die Beklagte beantragte die Abweisung der Klage und machte widerklageweise geltend, es sei festzustellen, dass sie dem Kläger nichts schulde.
Mit Entscheid vom 11. Februar 2013 wies das Kantonsgericht von Appenzell Ausserrhoden die Klage ab. In Gutheissung der Widerklage stellte es fest, dass die Beklagte dem Kläger aus dem Arbeitsverhältnis nichts mehr schulde.
B.b. Gegen diesen Entscheid erhob der Kläger Berufung an das Obergericht Appenzell Ausserrhoden, welches die Berufung mit Entscheid vom 1. Juli 2013 abwies.
C.
Mit Beschwerde in Zivilsachen beantragt der Kläger dem Bundesgericht, der Entscheid des Obergerichts Appenzell Ausserrhoden vom 1. Juli 2013 sei aufzuheben und die Klage gutzuheissen. Die negative Feststellungswiderklage der Beklagten sei abzuweisen, sofern überhaupt darauf eingetreten werden könne. Eventualiter sei die Streitsache zur Durchführung weiterer Abklärungen an die Vorinstanz zurückzuweisen. Ferner beantragt der Kläger, es sei von seinem Nachklagerecht Vormerk zu nehmen.
Die Beschwerdegegnerin beantragt die Abweisung der Beschwerde, soweit darauf einzutreten sei. Die Vorinstanz hat auf eine Vernehmlassung verzichtet.
Der Beschwerdeführer hat unaufgefordert eine Replik, die Beschwerdegegnerin eine Duplik eingereicht.
D.
Mit Präsidialverfügung vom 23. September 2013 wurde der Beschwerde die aufschiebende Wirkung erteilt.

Erwägungen:
1.
Das Bundesgericht prüft von Amtes wegen und mit freier Kognition, ob ein Rechtsmittel zulässig ist (<ref-law>; <ref-ruling> E. 1 S. 417 mit Hinweisen).
Der angefochtene Entscheid des Obergerichts Appenzell Ausserrhoden ist ein verfahrensabschliessender Endentscheid (<ref-law>) einer letzten kantonalen Instanz (<ref-law>). Der für die Beschwerde in Zivilsachen in arbeitsrechtlichen Fällen erforderliche Streitwert nach <ref-law> ist gegeben. Da auch die übrigen Sachurteilsvoraussetzungen erfüllt sind, ist - unter Vorbehalt einer rechtsgenüglichen Begründung (Art. 42 Abs. 2 i.V.m. <ref-law>) - auf die Beschwerde einzutreten.
2.
2.1. Mit Beschwerde in Zivilsachen können Rechtsverletzungen gemäss Art. 95 und 96 BGG gerügt werden. Gemäss <ref-law> hat die Rechtsschrift die Begehren und deren Begründung zu enthalten; im Rahmen der Begründung ist in gedrängter Form darzulegen, inwiefern der angefochtene Akt Recht verletzt (<ref-law>), andernfalls wird darauf nicht eingetreten. Unerlässlich ist im Hinblick auf <ref-law>, dass die Beschwerde auf die Begründung des angefochtenen Entscheids eingeht und im Einzelnen aufzeigt, worin eine Verletzung von Bundesrecht liegt. Der Beschwerdeführer soll in der Beschwerdeschrift nicht bloss die Rechtsstandpunkte, die er im kantonalen Verfahren eingenommen hat, erneut bekräftigen, sondern mit seiner Kritik an den als rechtsfehlerhaft erachteten Erwägungen der Vorinstanz ansetzen (vgl. <ref-ruling> E. 2.1 S. 245 f.).
2.2. Das Bundesgericht legt seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (<ref-law>). Von diesen tatsächlichen Feststellungen kann es nur dann abweichen, wenn sie offensichtlich unrichtig sind oder auf einer Rechtsverletzung im Sinne von <ref-law> beruhen (<ref-law>) und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>). Offensichtlich unrichtig bedeutet dabei willkürlich (<ref-ruling> E. 4.1.2 S. 62; <ref-ruling> E. 2.4 S. 313 f.; je mit Hinweisen).
Die Partei, welche die Sachverhaltsfeststellungen der Vorinstanz anfechten will, muss klar und substanziiert aufzeigen, inwiefern die gerügten Feststellungen bzw. die Unterlassung von Feststellungen offensichtlich unrichtig sind oder auf einer Rechtsverletzung im Sinne von <ref-law> beruhen (vgl. <ref-ruling> E. 1.2 S. 511 f.; <ref-ruling> E. 1.4.3 S. 254 f.). Überdies hat sie darzutun, inwiefern die Behebung des gerügten Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>; <ref-ruling> E. 2.2.2 S. 22). Auf eine Kritik an den tatsächlichen Feststellungen der Vorinstanz, die diesen Anforderungen nicht genügt, namentlich auf rein appellatorische Kritik an der Beweiswürdigung, ist nicht einzutreten (BGE <ref-ruling> E. 1.4.3 S. 254 f.).
Zu beachten ist, dass das Bundesgericht in die Beweiswürdigung des Sachgerichts nur eingreift, wenn diese willkürlich ist. Willkür im Sinne von <ref-law> liegt nach der Rechtsprechung nicht schon dann vor, wenn eine andere Lösung ebenfalls vertretbar erscheint oder gar vorzuziehen wäre. Das Bundesgericht hebt einen kantonalen Entscheid wegen Willkür nur auf, wenn er im Ergebnis unhaltbar ist (<ref-ruling> E. 2.2.2 S. 318 f.; <ref-ruling> E. 2.1 S. 9). Zudem steht dem Sachgericht im Bereich der Beweiswürdigung ein erheblicher Ermessensspielraum zu. Die Beweiswürdigung ist daher nur willkürlich, wenn das Sachgericht sein Ermessen missbraucht, indem es zum Beispiel offensichtlich unhaltbare Schlüsse zieht oder erhebliche Beweise übersieht (<ref-ruling> E. 4.2 S. 234 mit Hinweisen). Inwiefern die Beweiswürdigung willkürlich sein soll, ist in der Beschwerde klar und detailliert aufzuzeigen.
2.3. Diese Grundsätze verkennt der Beschwerdeführer. Seine Ausführungen erschöpfen sich weitgehend in appellatorischer Kritik am angefochtenen Entscheid. Er setzt sich zu grossen Teilen nicht oder nicht hinreichend mit den vorinstanzlichen Erwägungen auseinander, sondern begnügt sich damit, im Wesentlichen das Gleiche vorzubringen, was er bereits vor der Vorinstanz vorgebracht hat. Ebenso erweitert er den Sachverhalt und weicht von den tatsächlichen Feststellungen der Vorinstanz ab, ohne rechtsgenügliche Sachverhaltsrügen zu erheben. Seine diesbezüglichen Ausführungen haben daher unbeachtet zu bleiben und es ist ausschliesslich auf den von der Vorinstanz festgestellten Sachverhalt abzustellen.
3.
In der Teilklage an das Kantonsgericht von Appenzell Ausserrhoden, behielt sich der Beschwerdeführer das Nachklagerecht für die noch nicht eingeklagten Forderungen (Anteil 13. Monatslohn, Korrektur Arbeitszeugnis) vor. Darauf erhob die Beschwerdegegnerin widerklageweise eine negative Feststellungsklage auf den Nichtbestand der gesamten Forderung.
3.1. Der Beschwerdeführer macht geltend, die Vorinstanz habe Bundesrecht verletzt, indem sie die von der Beschwerdegegnerin erhobene negative Feststellungswiderklage als zulässig erachtet und keine materiell-rechtliche Prüfung der mit Nachklagerecht vorbehaltenen Ansprüche vorgenommen habe.
Ein Rechtsschutzinteresse für eine negative Feststellungsklage könne erst dann vorliegen, wenn die Interessen des Feststellungsklägers im Vergleich zu jenen des Teilklägers höher zu gewichten seien. Die Vorinstanz habe jedoch das Feststellungsinteresse der Widerklägerin voraussetzungslos bejaht, ohne zu prüfen, ob ein solches vorgelegen habe noch worin ein solches bestehen könnte. Ein Rechtsschutzinteresse an einer gemeinsamen Beurteilung aller Ansprüche aus dem Arbeitsverhältnis sei im Übrigen von der Beschwerdegegnerin auch gar nie geltend gemacht worden. Diese habe die Widerklage "aus rein prozesstaktischen Gründen eingesetzt, mit dem Ziel dem Beschwerdeführer zu schaden".
Von der Eintretensfrage sei sodann die materielle Beurteilung der Feststellungsklage zu unterscheiden. Aus der Zulassung der Feststellungswiderklage könne nicht auf eine Pflicht des Beschwerdeführers zur Substanziierung der weiteren (vorbehaltenen) Ansprüche geschlossen werden. Allein der Umstand, im Zeitpunkt der Hauptverhandlung vom Vorbringen weiterer Ansprüche abzusehen, könne nicht zu einer Gutheissung der unbegründeten und unsubstanziierten Widerklage führen.
3.2. Die Vorinstanz hielt fest, das Feststellungsinteresse der beklagten Partei sei ohne Weiteres zu bejahen, wenn sie auf eine Teilklage mit der Erhebung einer Widerklage auf Feststellung des Nichtbestandes des Gesamtanspruches reagiere. Das erstinstanzliche Gericht habe im Übrigen die Interessen der Parteien zutreffend gewürdigt und dabei zu Recht festgehalten, dass die Beschwerdegegnerin ein schutzwürdiges Interesse an einer sofortigen Entscheidung über die gesamten Ansprüche aus dem Arbeitsverhältnis habe.
3.3. Soweit der Beschwerdeführer geltend macht, ein Feststellungsinteresse der Beschwerdegegnerin habe gesondert geprüft werden müssen, gehen seine Vorbringen fehl. Das Bundesgericht bejaht nach konstanter Rechtsprechung das rechtliche Interesse der beklagten Partei, gegen die eine Teilklage erhoben wurde, durch Widerklage den Nichtbestand des behaupteten Anspruchs bzw. des Schuldverhältnisses feststellen zu lassen (Urteil 4A_80/2013 vom 30. Juli 2013 E. 6.4; 4A_255/2010 vom 29. Juni 2010 E. 5.5; je mit Hinweisen). Dies rührt daher, dass die Erhebung einer Leistungsklage die Anmassung nicht nur des eingeklagten Teilanspruchs selbst, sondern zugleich des gesamten Forderungsrechts als deren notwendige Grundlage bedeutet und deshalb die Beklagte in diesem vollen Umfang durch die gegen sie erhobene Klage in ihrer Privatrechtssphäre beeinträchtigt wird (Urteil 5C.252/2006 vom 1. Mai 2007 E. 5.1 mit Hinweis auf BGE 42 II 696 E. 4 S. 701). Die Vorinstanz hat demnach ohne Verletzung von Bundesrecht erwogen, dass das Feststellungsinteresse der beklagten Partei an einer gemeinsamen Beurteilung aller Ansprüche aus dem Arbeitsverhältnis ohne Weiteres zu bejahen ist.
Eine Verletzung von Bundesrecht ist auch nicht ersichtlich, soweit der Beschwerdeführer vorbringt, die Vorinstanz bzw. das erstinstanzliche Gericht habe keine materiell-rechtliche Prüfung der mit seinem Nachklagerecht vorbehaltenen Ansprüche (Anteil 13. Monatslohn, Korrektur Arbeitszeugnis) vorgenommen. Aus den Feststellungen des erstinstanzlichen Gerichts, auf welche die Vorinstanz ausdrücklich verweist, geht hervor, dass alle Ansprüche aus dem Arbeitsverhältnis am 31. August 2012 fällig geworden sind. Dabei hat das Kantonsgericht festgehalten, der Beschwerdeführer habe sich somit an der Einzelrichterverhandlung vom 9. Oktober 2012 nicht mehr auf sein Nachklagerecht berufen können, sondern habe die neu fälligen Ansprüche einklagen sollen. Da der Beschwerdeführer jedoch keine weiteren Ansprüche eingeklagt habe, sei die Widerklage gutzuheissen und festzustellen, dass die Beschwerdegegnerin dem Beschwerdeführer aus dem Arbeitsverhältnis nichts mehr schulde. Der Beschwerdeführer bringt keineswegs vor, weshalb es ihm nicht möglich oder zumutbar gewesen wäre, seine Ansprüche genügend zu substanziieren. Ebenso wenig zeigt er auf und es ist denn auch nicht ersichtlich, inwiefern die Vorinstanz bundesrechtswidrige Anforderungen an die Substanziierung gestellt hätte. Ein entsprechendes Vorbringen hat er auch vor der Vorinstanz nicht vorgebracht.
4.
Der Beschwerdeführer rügt sodann eine Verletzung von <ref-law> und macht geltend, die Vorinstanz habe ein unkorrektes Beweisthema gewählt, wesentliche Beweisanträge abgelehnt, eine unzulässige antizipierte Beweiswürdigung vorgenommen und die Beweise einseitig gewürdigt.
4.1. Der Beschwerdeführer bringt vor, die Vorinstanz habe in antizipierter Beweiswürdigung angenommen, die Voraussetzungen einer missbräuchlichen Kündigung seien nicht erfüllt. Dabei habe sie zu Unrecht die von ihm beantragten Zeugen - B._, C._, D._ sowie die behandelnde Ärzte Dr. E._ und Dr. A._ - nicht einvernommen. Diese hätten die verminderte Leistungsfähigkeit des Beschwerdeführers im Zeitpunkt der Kündigung bestätigen können bzw. hätten bestätigen können, dass der Beschwerdeführer am 16. Februar 2012 nicht in der Lage gewesen sei, Mehrarbeit zu leisten. Ebenso hätten B._, C._ und D._ aufzeigen können, dass die "massiven gesundheitlichen Probleme des Beschwerdeführers" zum massgeblichen Zeitpunkt der Kündigung den Mitarbeitern sowie den Vorgesetzten der Beschwerdegegnerin "offensichtlich klar und bekannt waren". Schliesslich hätte die Einvernahme der beantragten Zeugen auch aufgezeigt, dass es dem Beschwerdeführer bei der Verweigerung der Mehrarbeit darum gegangen sei, ein Überstundenpensum von 1 bis 2 Stunden pro Tag abzuwenden, welches ihm krankheitsbedingt nicht habe zugemutet werden können.
Darüber hinaus habe die Vorinstanz bezüglich dem Ausmass und der Dauer der zu leistenden Mehrarbeit, den erheblich eingeschränkten Beweiswert der Aussagen des Produktionsleiters und des Geschäftsführers der Beschwerdegegnerin missachtet und sich nicht mit den inhaltlichen Widersprüchen dieser Aussagen auseinander gesetzt.
4.2. Die Vorinstanz hielt fest, entscheidend sei, ob der Produktionsleiter und der Geschäftsführer der Beschwerdegegnerin am 16. Februar 2012 gewusst haben, dass der Beschwerdeführer aus gesundheitlichen Gründen nicht in der Lage gewesen sei, Überstunden zu leisten. Auch unter Zugrundelegung des Beweismasses der hohen Wahrscheinlichkeit habe der Beschwerdeführer einen solchen Beweis nicht erbringen können. Daran ändere auch das nachträgliche Attest von Dr. A._ vom 4. Juni 2012 nichts, wonach der Beschwerdeführer am 16. Februar 2012 seine Arbeit nicht habe ausüben können. Das Wissen um die verminderte Leistungsfähigkeit des Beschwerdeführers habe der Geschäftsführer der Beschwerdegegnerin am 16. Februar 2012 schlicht nicht haben können. So habe auch Dr. A._ erst nach der Operation des Beschwerdeführers und der damaligen genauen Diagnose einen Rückschluss auf den 16. Februar 2012 ziehen können.
Ebenso wenig habe der Beschwerdeführer glaubhaft machen können, er hätte für die Fertigstellung des Projekts rund 200 Überstunden leisten müssen; aus den Aussagen des Produktionsleiters und des Geschäftsführers der Beschwerdegegnerin gehe vielmehr hervor, es habe sich um eine einmalige Überzeit von ca. einer halben bis zwei Stunden gehandelt. Daran ändere auch die Einholung weiterer Produktionsunterlagen nichts, da diesen nicht entnommen werden könne, wie viele Überstunden vom Beschwerdeführer am 16. Februar 2012 verlangt wurden. Im Übrigen seien viele Beweisanträge im Lichte von <ref-law> verspätet.
Der Geschäftsführer der Beschwerdegegnerin habe somit am 16. Februar 2012 von der vollständigen Arbeitsfähigkeit des Beschwerdeführers ausgehen dürfen; eine missbräuchliche Kündigung liege unter diesen Umständen nicht vor. Auf die Abnahme weiterer Beweise könne daher verzichtet werden.
4.3. Gemäss <ref-law> hat, wo es das Gesetz nicht anders bestimmt, derjenige das Vorhandensein einer behaupteten Tatsache zu beweisen, der aus ihr Rechte ableitet (<ref-ruling> E. 3.1 S. 323; <ref-ruling> E. 2a/aa S. 273 mit Hinweisen). Wenn die Vorinstanz in Würdigung der vorhandenen Beweise eine rechtserhebliche Tatsache als bewiesen oder als widerlegt erachtet, liegt Beweiswürdigung vor und eine Verletzung von <ref-law>, der an die Beweislosigkeit anknüpft, fällt ausser Betracht (<ref-ruling> E. 5.4 S. 601 f.).
<ref-law> regelt die Beweiswürdigung nicht und schliesst auch die antizipierte Würdigung von Beweisen nicht aus (<ref-ruling> E. 5.4 S. 602; <ref-ruling> E. 3c S. 223 f.). Es ist dem Gericht somit nicht verboten, einem beantragten Beweismittel die Erheblichkeit oder Tauglichkeit abzusprechen oder auf die Abnahme von (weiteren) Beweisen zu verzichten, wenn es aufgrund der bereits abgenommenen Beweisen seine Überzeugung bereits gebildet hat und willkürfrei davon ausgehen darf, diese würde durch weitere Beweiserhebungen nicht geändert (<ref-ruling> E. 5.4 S. 602; <ref-ruling> E. 2.6 S. 24 f.).
4.4. Der Beschwerdeführer stellt sich bezüglich des Beweisthemas auf den Standpunkt, entscheidend sei nicht das Wissen der Beschwerdegegnerin um seine verminderte Arbeitsfähigkeit im Zeitpunkt der Kündigung, sondern ob ihm aufgrund seiner eingeschränkten Leistungsfähigkeit ein Arbeitspensum von mehr als 100 % möglich und zumutbar gewesen sei. Dieser Auffassung kann nicht gefolgt werden: Für das Vorliegen einer missbräuchlichen Kündigung muss bereits das Motiv der Kündigung missbräuchlich sein und zwischen dem missbräuchlichen Grund und der Kündigung ein Kausalzusammenhang bestehen. Da der Kläger die Beweislast für die Missbräuchlichkeit der Kündigung trägt, muss er beweisen, dass ihm tatsächlich aus einem missbräuchlichen Grund gekündigt worden ist. Entscheidend ist demnach, wie die Vorinstanz festgehalten hat, ob die Beschwerdegegnerin am 16. Februar 2012 gewusst hat, dass der Kläger aus gesundheitlichen Gründen nicht in der Lage war, Überstunden zu leisten. Soweit der Beschwerdeführer vorbringt, die Vorinstanz hätte bezüglich seiner verminderten Leistungsfähigkeit bzw. der Unzumutbarkeit Mehrarbeit zu leisten die von ihm beantragten Zeugen einvernehmen sollen, verkennt er, dass die betreffenden Fragen für den Entscheid nicht erheblich waren. Nach <ref-law> ist Beweis lediglich über erhebliche Tatsachen abzunehmen, nicht aber über solche, die nichts am Entscheid zu ändern vermöchten (<ref-ruling> E. 2.3 S. 226).
Soweit der Beschwerdeführer vorbringt, die beantragten Zeugen hätten auch aufgezeigt, "dass die massiven gesundheitlichen Probleme des Beschwerdeführers zum massgeblichen Zeitpunkt der Kündigung den Mitarbeitern wie auch den Vorgesetzten (...) offensichtlich klar und bekannt waren", bezieht er sich zwar auf das relevante Beweisthema. Er zeigt aber nicht auf, einen entsprechenden Beweisantrag bereits in den kantonalen Verfahren form- und fristgerecht gestellt zu haben. <ref-law> gibt der beweisbelasteten Partei einen Anspruch darauf, für rechtserhebliche Sachvorbringen zum Beweis zugelassen zu werden, sofern ihr Beweisantrag nach Form und Inhalt den Vorschriften des anwendbaren Verfahrensrechts entspricht (<ref-ruling> E. 5.2.2 S. 195; <ref-ruling> E. 3 S. 157; <ref-ruling> E. 2 S. 242; je mit Hinweisen). Ein Beweismittel ist nur dann als formgerecht angeboten zu betrachten, wenn sich die Beweisofferte eindeutig der damit zu beweisenden Tatsachenbehauptung zuordnen lässt. Aus dem in der Beschwerde zitierten Aktenhinweis (S. 3 der Plädoyernotizen vor dem Kantonsgericht), geht hervor, dass der Beschwerdeführer die Einvernahme der genannten Zeugen für den Nachweis, dass er nicht in der Lage gewesen sei, Mehrarbeit zu leisten, beantragt hat. Der Beschwerdeführer zeigt jedoch nicht auf, die Zeugen auch hinsichtlich des Wissens der Beschwerdegegnerin um seine verminderte Leistungsfähigkeit offeriert zu haben, wie er dies nun im bundesgerichtlichen Verfahren vorbringt. An der vom Beschwerdeführer angegebenen Stelle befindet sich keine Beweisofferte zu diesem Thema. Bei dieser Sachlage verletzte die Vorinstanz kein Bundesrecht, wenn sie von der Einvernahme der beantragten Zeugen absah und in (vorweggenommener) Beweiswürdigung festgestellt hat, dass auch mit weiteren (anderen) Beweisabnahmen mit hoher Wahrscheinlichkeit das Wissen der Beschwerdegegnerin um die verminderte Leistungsfähigkeit des Beschwerdeführers nicht nachgewiesen werden kann.
4.5. Schliesslich vermag der Beschwerdeführer auch die vorinstanzlichen Beweiswürdigung, wonach der Produktionsleiter und der Geschäftsführer der Beschwerdegegnerin am 16. Februar 2012 schlicht nicht haben wissen können, dass der Beschwerdeführer nicht zu 100 % arbeitsfähig gewesen sei, nicht als willkürlich auszuweisen. Seine Vorbringen erschöpfen sich weitgehend in appellatorischer Kritik (vgl. E. 2.2). Er legt insbesondere nicht dar, was das Attest von Dr. A._ vom 4. Juni 2012, welcher nachträglich bescheinigte, dass der Beschwerdeführer die verlangte Mehrarbeit nicht hätte leisten können, am Wissensstand der Beschwerdegegnerin hätte ändern sollen. Zwar mag zutreffen, dass Dr. A._ als behandelnder Arzt des Beschwerdeführers genaue Kenntnisse über den am 16. Februar 2012 vorliegenden Gesundheitszustand des Beschwerdeführers hatte, so dass die Tatsache, dass sein Attest fast vier Monate später ausgestellt wurde, nicht gegen den Beweiswert hinsichtlich des bescheinigten Gesundheitszustands spricht. Dies ändert aber, wie die Vorinstanz festgestellt hat, nichts daran, dass für den 16. Februar 2012 kein ärztliches Attest vorlag, weshalb die Beschwerdegegnerin nicht von einer verminderten Arbeitsfähigkeit hat ausgehen können und müssen. Daran vermögen schliesslich auch die Vorbringen des Beschwerdeführers bezüglich dem Ausmass und der Dauer der angeordneten Mehrarbeit nichts zu ändern. Im Übrigen verhält er sich widersprüchlich, indem er einerseits vorbringt, eine Mehrarbeit habe ihm aufgrund seiner Leiden nicht zugemutet werden dürfen, andererseits wäre er aber "zweifelsohne" für eine einmalige Mehrarbeit bis zum Operationstermin zur Verfügung gestanden.
4.6. Der Vorinstanz kann demnach weder Willkür in ihrer Beweiswürdigung noch eine Verletzung von <ref-law> vorgeworfen werden. Sie hat zu Recht erwogen, dass kein missbräuchliches Motiv für die Kündigung vom 16. Februar 2012 vorgelegen hat.
5.
Die Beschwerde erweist sich als unbegründet. Sie ist abzuweisen, soweit darauf einzutreten ist. Bei diesem Verfahrensausgang wird der Beschwerdeführer kosten- und entschädigungspflichtig (Art. 66 Abs. 1 sowie Art. 68 Abs. 2 BGG). Mit Blick auf den Streitwert und die Natur der Streitigkeit kommen reduzierte Kosten in Ansatz (<ref-law>). Dagegen ist die volle Parteientschädigung geschuldet.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Die Gerichtskosten von Fr. 600.-- werden dem Beschwerdeführer auferlegt.
3.
Der Beschwerdeführer hat die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 2'500.-- zu entschädigen.
4.
Dieses Urteil wird den Parteien und dem Obergericht Appenzell Ausserrhoden, Einzelrichter, schriftlich mitgeteilt.
Lausanne, 28. Oktober 2013
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Klett
Die Gerichtsschreiberin: Reitze