nachträgliche Baubewilligung (Ausnahmebewilligung), hat sich ergeben:
A.- S._ ist Eigentümer der Parzelle Nr. 340, Schwellbrunn. Darauf befindet sich ein ca. hundertjähriges Wohnhaus in Kreuzgiebelbauweise mit Treppenhausanbau an der Nordwestseite (strassenseitig). Das Grundstück liegt ausserhalb der Bauzone. Mit Baugesuch vom 15. April 1992 ersuchte S._ um Bewilligung für einen Umbau des Hauses. Die Baudirektion des Kantons Appenzell Ausserrhoden bewilligte am 5. Juni 1992 das Vorhaben nur teilweise und verband damit unter anderem die Auflage, den Treppenhausanbau mit der Verlängerung des bestehenden Quergiebels zu überdecken.
Am 20. Juli 1992 reichte S._ ein überarbeitetes Bauprojekt ein, welches unter anderem die verlangte Giebelüberdeckung des Treppenhausanbaus und auf der Südostseite im ersten Obergeschoss einen Balkon enthielt. Am 14. September 1992 erteilte die Baudirektion die Baubewilligung mit einigen Auflagen. In der Folge wurde anlässlich einer Baukontrolle festgestellt, dass die Bauausführung erheblich vom bewilligten Projekt abwich. Nebst anderen nicht mehr streitigen Punkten war auf der Südostseite anstelle des bewilligten einen Balkons im ersten Obergeschoss ein bis ins zweite Obergeschoss reichender Balkonanbau erstellt und der darüber liegende Kreuzgiebel zu einem Balkondach erweitert worden. Am 18. Mai 1994 reichte S._ ein nachträgliches Baugesuch ein, welches am 6. September 1994 nur teilweise bewilligt wurde. Nicht bewilligt wurde unter anderem der zweigeschossige Balkonanbau mit Überdachung; es wurde dessen Abbruch bis auf den ursprünglich bewilligten Balkon im ersten Obergeschoss verfügt.
S._ erhob dagegen erfolglos Rekurs an den Regierungsrat und anschliessend Beschwerde an das Verwaltungsgericht des Kantons Appenzell Ausserrhoden. Dieses wies die Beschwerde mit Urteil vom 29. September 1999, versandt am 1. Februar 2000, im hier noch streitigen Punkt ab.
B.- S._ erhob mit Eingabe vom 2. März 2000 (Postaufgabe 3. März 2000) Beschwerde an das Bundesgericht.
Mit Schreiben vom 16. März 2000 setzte das Bundesgericht S._ gemäss Art. 108 Abs. 3 OG eine Nachfrist an. Innert Frist reichte S._ Verwaltungsgerichtsbeschwerde ein mit dem Rechtsbegehren, das Urteil des Verwaltungsgerichts insoweit aufzuheben, als die Baubewilligung für den Balkonanbau über dem 1. Obergeschoss inkl. Überdachung verweigert und der Abbruch bestätigt wurde. Demgemäss sei die Baubewilligung für den Balkonanbau über dem 1. Obergeschoss inklusive der Überdachung zu erteilen. Eventualiter sei das Urteil hinsichtlich Balkonanbaute über dem 1. Obergeschoss und Überdachung aufzuheben und die Angelegenheit zur erneuten Beurteilung und Entscheidung an die Vorinstanz zurückzuweisen.
C.- Der Regierungsrat des Kantons Appenzell Ausserrhoden beantragt, die Beschwerde abzuweisen, soweit darauf eingetreten werden könne. Das Verwaltungsgericht und das Bundesamt für Raumentwicklung schliessen auf Abweisung der Beschwerde.
D.- Mit Verfügung des Präsidenten der I. öffentlichrechtlichen Abteilung des Bundesgerichts vom 12. Mai 2000 wurde der Beschwerde aufschiebende Wirkung zuerkannt.

Das Bundesgericht zieht in Erwägung:
1.- a) Der angefochtene Entscheid des Verwaltungsgerichts stützt sich materiellrechtlich im Wesentlichen auf Art. 80 Abs. 2 und Art. 77 Abs. 2 des kantonalen Gesetzes vom 28. April 1985 über die Einführung des Bundesgesetzes über die Raumplanung (EG zum RPG). Er betrifft jedoch - soweit hier streitig - eine Ausnahmebewilligung im Sinne von Art. 24 RPG. Die Verwaltungsgerichtsbeschwerde an das Bundesgericht ist daher zulässig (Art. 34 Abs. 1 RPG). Der Beschwerdeführer ist als Verfügungsadressat zur Verwaltungsgerichtsbeschwerde legitimiert (Art. 103 lit. a OG). Auf die form- und fristgerecht eingereichte Verwaltungsgerichtsbeschwerde ist einzutreten.
Im Rahmen der Verwaltungsgerichtsbeschwerde kann auch die Verletzung kantonalen Rechts aus dem Anwendungsbereich von Art. 24 RPG gerügt werden. Das kantonale Recht, welches im Sinne von Art. 24 Abs. 2 RPG die Erneuerung, die teilweise Änderung oder den Wiederaufbau von Bauten und Anlagen gestattet, kann dabei jedoch als selbständiges kantonales Recht nur auf Willkür hin überprüft werden (<ref-ruling> E. 1 S. 10; <ref-ruling> E. 2 S. 96 f.).
b) Das Rechtsbegehren der Beschwerde bezieht sich ausdrücklich nur auf die Frage des Balkonanbaus über dem
1. Obergeschoss inklusive Überdachung. Die übrigen im kantonalen Verfahren noch streitigen Punkte bilden nicht Gegenstand des bundesgerichtlichen Verfahrens.
2.- Der Beschwerdeführer bringt vor, das Verwaltungsgericht habe ausgeführt, die streitige Anbaute könne nicht als blosse teilweise Änderung qualifiziert werden. Diese Ansicht sei unhaltbar. Der Anbau stelle eine teilweise Änderung im Sinne von Art. 24 Abs. 2 RPG dar.
Es trifft zu, dass im angefochtenen Urteil ausgeführt wird, der Anbau könne nicht als teilweise Änderung qualifiziert werden. Zuvor führt das Verwaltungsgericht jedoch aus, eine teilweise Änderung könne gemäss Art. 80 Abs. 2 EG zum RPG bewilligt werden, wenn unter anderem Art. 77 dieses Gesetzes eingehalten sei. Gemäss Art. 77 Abs. 2 EG zum RPG hätten sich Neubauten, Umbauten und Renovationen der herkömmlichen Bauart zumindest in Bezug auf Gebäude- und Dachform sowie Material- und Farbwahl anzupassen.
Diese Bestimmung gehe über ein blosses Verunstaltungsverbot hinaus und verlange positiv eine gute Gestaltung. Das bedeute, dass an traditionellen Bauten stilgerechte Bauteile verlangt und stilfremde untersagt werden könnten. In der Folge beurteilte das Verwaltungsgericht den streitigen Balkonanbau mit Überdachung im Lichte der Kriterien von Art. 77 Abs. 2 EG zum RPG und kam zum Ergebnis, die nachträgliche Baubewilligung sei dafür mit Recht verweigert worden. Auch bei der Beurteilung, ob die Abbruchverfügung verhältnismässig sei, stützt sich das Verwaltungsgericht auf Art. 77 Abs. 2 EG zum RPG. Es hat damit diejenigen Kriterien angewendet, welche gemäss Art. 80 Abs. 2 lit. c EG zum RPG für die Bewilligung einer teilweisen Änderung massgebend sind. Selbst wenn die Ansicht des Beschwerdeführers, der streitige Anbau sei eine teilweise Änderung, richtig sein sollte, kann daher das Vorgehen des Verwaltungsgerichts im Ergebnis nicht beanstandet werden.
3.- a) Der Beschwerdeführer rügt, das Verwaltungsgericht habe den Ursprung der ganzen Auseinandersetzung vernachlässigt.
Der im Jahre 1992 projektierte Umbau sei die direkte Folge der vom Kanton beabsichtigten Strassenverbreiterung gewesen. Infolge dieser Verbreiterung habe der strassenseitige Treppenhausanbau umgestaltet werden müssen. Die Baudirektion habe mit Verfügung vom 5. Juni 1992 verlangt, den Treppenhausanbau mit der Verlängerung des bestehenden Quergiebels zu überdecken. Bei der Ausführung dieser Arbeiten habe sich herausgestellt, dass die Dachstruktur teilweise verfault und morsch gewesen sei. Er habe sich daher entschlossen, die gesamte Dachstruktur zu erneuern und den Quergiebel auch Richtung Süden zu verlängern. Der erste markante Eingriff in das Kreuzgiebelgebäude habe somit im Jahre 1992 als direkte Folge des Staatsstrassenbaus stattgefunden, wodurch die ursprüngliche Symmetrie des Gebäudes verändert worden sei. Es sei unhaltbar, nun bei geringfügigen Änderungen wieder auf die herkömmliche Bauart und das Einordnungsgebot zu verweisen.
b) Die sachverhaltsmässigen Vorbringen des Beschwerdeführers ergeben sich im Wesentlichen aus den Akten und stellen daher keine unzulässigen Noven dar.
c) Aufgrund der Akten trifft es zu, dass die Umgestaltung des Treppenhausanbaus eine direkte Folge des Strassenbaus darstellt und die Verlängerung des nordwestlichen Quergiebels sogar auf eine ausdrückliche Anordnung des Kantons zurückgeht. Fehl geht jedoch der Einwand des Beschwerdeführers, der 1992 bewilligte markante Eingriff in das Kreuzgiebelgebäude sei überwiegend durch die Korrektion der Staatsstrasse initiiert worden, weshalb es unverhältnismässig sei, den streitigen Balkonanbau am Zustand des Hauses vor 1992 zu messen. Direkte Folge des Strassenbaus war nur die Anpassung des Treppenhausanbaus. Die übrigen Elemente des Umbaus, namentlich die 1992 bewilligte Einstellhalle, die Terrasse mit Treppenaufgang sowie der vorliegend streitige Balkonanbau waren hingegen nicht notwendige Folge der Strassenkorrektion. Es ist zwar verständlich, dass der Beschwerdeführer diesen Umbau zugleich mit den durch die Strassenverbreiterung verursachten Arbeiten ausführte. Das ändert aber nichts daran, dass kein direkter Zusammenhang zwischen diesen Umbauten und dem Strassenbau besteht.
d) Es kann auch nicht gesagt werden, dass die von der Baudirektion 1992 verlangte Verlängerung des nordwestlichen Quergiebels einen so markanten Eingriff in das Gebäude verursacht hätte, dass die jetzt streitige Balkonanbaute nur noch eine weitere geringfügige Änderung des Erscheinungsbildes darstellen würde. Aus den bei den Akten liegenden Fotos geht hervor, dass die Verlängerung des nordwestlichen Quergiebels zwar die vorher bestehende Symmetrie des Daches aufhob, dafür aber den Giebel bis zur Fassade des Treppenhausanbaus erweiterte und insofern das Erscheinungsbild demjenigen des klassizistischen Kreuzgiebelgebäudes annäherte.
Demgegenüber stellt der streitige Balkonanbau auf der südöstlichen Seite ein eindeutig stilfremdes Element dar, welches das Erscheinungsbild der Fassade wesentlich verändert.
Der verlängerte Quergiebel stellt zwar die Symmetrie des Daches wieder her, kragt jedoch deutlich über die Hausfassade hervor, was dem herkömmlichen Erscheinungsbild des Appenzeller Hauses nicht entspricht.
e) Einzuräumen ist, dass das ursprüngliche Erscheinungsbild der südöstlichen Fassade bereits durch die 1992 bewilligte Einstellhalle wesentlich verändert wurde. Dabei ist jedoch zu berücksichtigen, dass diese im Gegensatz zu den Wohnungen zonenkonform ist. Zudem hat sie zumindest das Erscheinungsbild des Hauses oberhalb der Terrasse im Wesentlichen unverändert gelassen. Aus dem Umstand, dass dem Beschwerdeführer die Einstellhalle bewilligt wurde, kann nicht ein Anspruch auf Bewilligung zusätzlicher stilfremder Elemente abgeleitet werden. Gesamthaft lässt sich die Verweigerung der nachträglichen Baubewilligung willkürfrei und ohne Verletzung des Verhältnismässigkeitsprinzips auf Art. 77 Abs. 2 EG zum RPG stützen.
4.- Der Beschwerdeführer rügt, die Wiederherstellung des ursprünglichen Zustandes sei unverhältnismässig.
a) Das Verwaltungsgericht geht davon aus, der Beschwerdeführer sei nicht gutgläubig von den bewilligten Plänen abgewichen. Was der Beschwerdeführer dagegen vorbringt, ist unbehelflich. Ihm musste zumindest aus dem vorangehenden Baubewilligungsverfahren bekannt sein, dass die Änderung des Projekts einer Bewilligung bedurft hätte. Dass sich im Rahmen des Umbaus herausstellte, dass das Dachgebälk schadhaft war, stellte keinen zwingenden Grund dar, den Giebel südlich zu verlängern. Sodann beziehen sich die Ausdrücke "gutgläubig" bzw. "bösgläubig" auf das Wissen um die Bewilligungspflicht.
Selbst wenn der Beschwerdeführer in guten Treuen der Ansicht war, durch die Verlängerung des südlichen Quergiebels werde die Symmetrie des Daches wieder hergestellt, musste ihm bewusst sein, dass diese Veränderung nicht ohne Bewilligung zulässig war.
b) Das Verwaltungsgericht hat ferner ausgeführt, dass sich auch derjenige, der bösgläubig ohne Baubewilligung gebaut hat, auf das Verhältnismässigkeitsprinzip berufen könne; er müsse aber in Kauf nehmen, dass die Behörden aus grundsätzlichen Erwägungen zum Schutze der Rechtsgleichheit und der baurechtlichen Ordnung dem öffentlichen Interesse an der Wiederherstellung des gesetzmässigen Zustandes erhöhtes Gewicht beimessen und die dem Bauherrn erwachsenden Nachteile nicht oder nur in verringertem Masse berücksichtigen.
Diese Auffassung ist zutreffend und entspricht der bundesgerichtlichen Rechtsprechung (<ref-ruling> E. 4a S. 255 mit Hinweis).
c) Im Lichte dieser Rechtsprechung ist das verwaltungsgerichtliche Urteil nicht zu beanstanden. Die Wiederherstellung ist entgegen der Ansicht des Beschwerdeführers durchaus geeignet, das Erscheinungsbild der südöstlichen Fassade dem herkömmlichen Kreuzgiebelstil zumindest wieder stark anzunähern. Es ist nicht ersichtlich, inwiefern sie weitergehende Eingriffe in das Dach oder in die Fassade zur Folge haben sollte. Wohl mag der fragliche Balkonanbau für sich allein betrachtet keine besonders schwere Verletzung raumplanerischer Prinzipien darstellen, doch haben die kantonalen Instanzen mit Recht die Bedeutung der Rechtsgleichheit und der präjudiziellen Auswirkungen betont. Das Gebot, Bauten in die Umgebung einzufügen, könnte nicht mehr durchgesetzt werden, wenn jeder Bauherr ohne Baubewilligung unzulässige Bauten erstellen und sich der Wiederherstellung unter Hinweis auf die entstehenden Kosten widersetzen könnte.
Der Beschwerdeführer hätte die Kosten vermeiden können, wenn er rechtzeitig um eine Baubewilligung nachgesucht hätte.
5.- Die Verwaltungsgerichtsbeschwerde erweist sich damit als unbegründet. Bei diesem Ausgang des Verfahrens sind die Gerichtskosten dem Beschwerdeführer aufzuerlegen (Art. 156 Abs. 1 OG).

Demnach erkennt das Bundesgericht:
1.- Die Verwaltungsgerichtsbeschwerde wird abgewiesen.
2.- Die Gerichtsgebühr von Fr. 2'000.-- wird dem Beschwerdeführer auferlegt.
3.- Dieses Urteil wird dem Beschwerdeführer, dem Gemeinderat Schwellbrunn, dem Regierungsrat des Kantons Appenzell A.Rh. und dem Verwaltungsgericht von Appenzell A.Rh., II. Abteilung, sowie dem Bundesamt für Raumentwicklung schriftlich mitgeteilt.
_
Lausanne, 10. Juli 2000
Im Namen der I. öffentlichrechtlichen Abteilung
des SCHWEIZERISCHEN BUNDESGERICHTS
Der Präsident:
Der Gerichtsschreiber: