Sachverhalt:
A. X._ reichte am 19. Januar 2006 ein Baugesuch betreffend Fassadensanierung seines Wohnhauses in Schwellbrunn ein. Das Planungsamt erteilte am 23. Februar 2006 die raumplanerische Bewilligung mit der Auflage, dass die zu ersetzenden Fenster auf der Wetterseite in Holz/Metall mit aussenliegenden Holzsprossen und mit Fensterzargen in Holz auszuführen seien. Den dagegen erhobenen Rekurs von X._ wies das Departement Bau und Umwelt des Kantons Appenzell Ausserrhoden (DBU) am 7. August 2007 ab. Das Verwaltungsgericht des Kantons Appenzell Ausserrhoden wies die dagegen erhobene Beschwerde mit Entscheid vom 23. Januar 2008 ab. Dieser Entscheid erwuchs in Rechtskraft, nachdem der Beschwerdeführer auf eine Begründung verzichtet hatte.
B. Am 8. Oktober 2007 zeigte X._ den Baubeginn an. Mit Schreiben vom 11. Oktober 2007 stellte er sich gegenüber der Baukommission auf den Standpunkt, im (damals noch hängigen) Beschwerdeverfahren stelle sich nur die Frage des Materials der Fensterrahmen. Er sicherte zu, dass er die Fensterrahmen bei der gegenwärtigen Renovation nicht ersetzen werde. Da er aber einen Grundsatzentscheid verlange, werde er seine Beschwerde nicht zurückziehen.
C. Am 24. Oktober 2007 verfügte der Gemeinderat Schwellbrunn einen vorläufigen Baustopp, da zufolge der aufschiebenden Wirkung der Beschwerde an das Verwaltungsgericht noch keine rechtskräftige Bewilligung vorliege und ein vorzeitiger Baubeginn nicht bewilligt worden sei. Den dagegen erhobenen Rekurs von X._ wies der Gemeinderat Schwellbrunn am 28. November 2007 ab und erlegte diesem eine Gebühr von Fr. 300.-- auf.
Dagegen erhob X._ am 11. Dezember 2007 "Rekurs" bzw. Aufsichtsanzeige beim Regierungsrat des Kantons Appenzell Ausserrhoden, der die Sache zuständigkeitshalber dem DBU überwies. Mit Entscheid vom 4. März 2008 wies das DBU den Rekurs ab. Zufolge Aussichtslosigkeit des Rechtsmittels wurde die beantragte unentgeltliche Rechtspflege verweigert und dem Rekurrenten eine Entscheidgebühr von Fr. 500.-- auferlegt.
D. Dagegen erhob X._ am 26. März 2008 Beschwerde an das Verwaltungsgericht. Dieses gewährte X._ am 9. Juni 2008 die unentgeltliche Rechtspflege. Am 17. Dezember 2008 trat es mangels Anfechtungsobjekts auf die Beschwerde nicht ein, weil der vorläufige Baustopp mit Eintritt der Rechtskraft der Baubewilligung ersatzlos dahingefallen sei. Die Entscheidgebühr von Fr. 1'500.-- wurde auf die Staatskasse genommen (vorbehältlich der Rückforderung für den Fall günstiger wirtschaftlicher Verhältnisse des Beschwerdeführers).
E. Gegen den verwaltungsgerichtlichen Entscheid erhob X._ mit Eingabe vom 14. April 2009 Beschwerde in öffentlich-rechtlichen Angelegenheiten ans Bundesgericht. Er beantragt, die Kostensprüche des Gemeinderats Schwellbrunn vom 28. November 2007, des DBU vom 4. März 2009 und des Verwaltungsgerichts vom 17. Dezember 2008 seien aufzuheben; eventualiter sei die Sache zu neuer Beurteilung an die Vorinstanz zurückzuweisen. Überdies ersucht er um Gewährung der unentgeltlichen Rechtspflege.
F. Das DBU schliesst auf Abweisung der Beschwerde, soweit darauf einzutreten sei. Der Gemeinderat Schwellbrunn beantragt sinngemäss Abweisung der Beschwerde. Das Verwaltungsgericht hat auf eine Vernehmlassung verzichtet.
In seiner Replik hält der Beschwerdeführer an seinen Anträgen fest.

Erwägungen:
1. Gegen den angefochtenen, kantonal letztinstanzlichen Entscheid steht die Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht grundsätzlich offen. Dabei kann offen bleiben, ob es sich beim vorläufigen Baustopp um einen Zwischenentscheid im Baubewilligungsverfahren oder um einen selbstständigen Entscheid gehandelt hat: Nachdem das Baubewilligungsverfahren inzwischen abgeschlossen worden ist und somit ein Endentscheid vorliegt, können zuvor ergangene Zwischenentscheide noch angefochten werden, soweit sie sich auf den Inhalt des Endentscheids auswirken (<ref-law>); gleiches gilt, sofern der Zwischenentscheid nur noch in Bezug auf die Kosten- und Entschädigungsfolgen angefochten wird (<ref-ruling> E. 2.2 in fine S. 648; Urteil 2C_759/2008 vom 6. März 2009 E. 2.7).
Der Beschwerdeführer, auf dessen Rechtsmittel im kantonalen Verfahren nicht eingetreten wurde, ist zur Beschwerde legitimiert, soweit er einen materiellen Entscheid des Verwaltungsgerichts verlangt (<ref-law>). Auf die rechtzeitig erhobene Beschwerde ist daher grundsätzlich einzutreten, vorbehältlich rechtsgenügend begründeter Rügen (<ref-law> i.V.m. <ref-law>).
Nicht einzutreten ist dagegen auf seine Rügen in der Sache und seine Anträge auf Aufhebung der Kostenentscheide des Gemeinderats Schwellbrunn und des DBU: Nachdem das Verwaltungsgericht auf die dagegen gerichtete Beschwerde nicht eingetreten war, liegt insoweit noch kein kantonal letztinstanzlicher Entscheid vor.
2. Das Verwaltungsgericht trat auf die Beschwerde nicht ein, weil die Baubewilligung bereits im Zeitpunkt der Beschwerdeerhebung rechtskräftig und damit der vorläufige Baustopp hinfällig gewesen sei, weshalb es an einem Anfechtungsobjekt fehle.
Der Beschwerdeführer räumt ein, dass das Verfahren betreffend Baustopp durch den rechtskräftigen Entscheid des Verwaltungsgerichts über die Baubewilligung gegenstandslos geworden sei. Er macht jedoch geltend, er habe sich mit seiner Beschwerde nicht mehr gegen den vorläufigen Baustopp, sondern ausschliesslich gegen die noch offenen Kostensprüche des Gemeinderats Schwellbrunn vom 28. November 2007 und des DBU vom 4. März 2008 gewendet. Er beruft sich auf die bundesgerichtliche Rechtsprechung, wonach ein Betroffener gegen einen Kostenentscheid Beschwerde führen könne, auch wenn ihm die Legitimation zur Anfechtung des Hauptsachenentscheids fehle. Das Verwaltungsgericht hätte deshalb auf die Beschwerde eintreten und über die Kostensprüche urteilen müssen.
3. Der Beschwerdeführer macht nicht die willkürliche Anwendung von kantonalem Prozessrecht geltend, sondern beruft sich einzig auf die bundesgerichtliche Rechtsprechung zur Legitimation vor Bundesgericht. Insofern ist lediglich zu prüfen, ob das Verwaltungsgericht die Beschwerdebefugnis enger gefasst hat als diejenige vor Bundesgericht (<ref-law>) und damit <ref-law> verletzt hat.
3.1 Nach ständiger bundesgerichtlicher Rechtsprechung kann ein Betroffener gegen einen Kostenentscheid Beschwerde führen, auch wenn ihm die Legitimation zur Anfechtung des Hauptentscheids fehlt, da er durch die Auferlegung von Gerichts- und/oder Parteikosten persönlich und unmittelbar in seinen Interessen betroffen ist (<ref-law>; so schon <ref-ruling> E. 1b S. 255 mit Hinweisen). Allerdings kann er nur geltend machen, die Kostenverlegung sei aus einem anderen Grund als dem blossen Umstand, dass er in der Hauptsache unterlag, verfassungs- oder bundesrechtswidrig (<ref-ruling>). Die Belastung mit Kosten verschafft ihm somit keine Möglichkeit, indirekt, über den Kostenentscheid, eine Überprüfung des Entscheids in der Hauptsache zu erlangen (<ref-ruling> E. 4 S. 299). Gleiches gilt, wenn ein Beschwerdeführer kein aktuelles Interesse mehr an der Anfechtung des Hauptsachenentscheids hat. Auch in diesen Fällen ist er zwar noch zur Anfechtung des vorinstanzlichen Kostenentscheids legitimiert, jedoch nur noch aus Gründen, die mit dem Entscheid in der Hauptsache in keinem unmittelbaren Zusammenhang stehen (Urteile 2P.275/2004 vom 16. März 2005 E. 6.2; 2P.214 und 215/2001 vom 30. Januar 2002 E. 3.3).
3.2 Mit seiner Beschwerde an das Verwaltungsgericht verlangte der Beschwerdeführer, der Entscheid des DBU vom 4. März 2008, die Verfügung des Gemeinderats Schwellbrunn vom 28. November 2007 sowie die Verfügung der Baukommission Schwellbrunn betreffend Baustopp vom 24. Oktober 2007 (die ohne Kosten erging) seien "vollumfänglich" aufzuheben. Die Kostenentscheide wurden weder im Antrag (z.B. in Form eines Eventualantrags) noch in der Begründung der Beschwerde besonders erwähnt. In der Beschwerdebegründung legte der Beschwerdeführer vielmehr dar, weshalb die Anordnung des vorläufigen Baustopps rechtswidrig gewesen sei. Damit erhob er gerade keine eigenständigen, vom Ausgang der Hauptsache unabhängigen, Rügen betreffend die Kostenentscheide, sondern verlangte eine Überprüfung der Hauptsache, d.h. des vorläufigen Baustopps, durch das Verwaltungsgericht.
3.3 Lediglich im letzten Absatz der Verwaltungsgerichtsbeschwerde findet sich ein Satz, wonach die Ablehnung der unentgeltlichen Rechtspflege wegen Aussichtslosigkeit durch das DBU haltlos gewesen sei.
Allerdings macht der Beschwerdeführer vor Bundesgericht nicht geltend, dieser Satz hätte vom Verwaltungsgericht als selbständige Rüge gegen die Versagung der unentgeltlichen Rechtspflege im Rekursverfahren vor dem DBU verstanden werden müssen. Insofern fehlt es diesbezüglich bereits an einer genügenden Beschwerdebegründung (Art. 106 Abs. 2 i.V.m. <ref-law>).
Der erwähnte Satz am Ende der Beschwerdebegründung ist auch nicht eindeutig, mündet er doch (am Ende des Absatzes) in das Begehren um Zusprechung einer Parteientschädigung. Hätte der Beschwerdeführer die Gewährung der unentgeltlichen Rechtspflege im Rekursverfahren erreichen wollen, hätte er sich auch nicht mit einem Antrag auf Aufhebung der vorinstanzlichen Entscheid begnügen dürfen, sondern hätte einen positiven Entscheid des Verwaltungsgerichts zu dieser Frage oder die Rückweisung der Sache an das DBU zu neuem Entscheid über die unentgeltliche Rechtspflege verlangen müssen.
4. Aufgrund aller Umstände durfte das Verwaltungsgericht deshalb davon ausgehen, dass der Beschwerdeführer einen Entscheid über den vorläufigen Baustopp verlangte und keine eigenständigen - vom Entscheid in der Hauptsache unabhängige - Rügen gegen die Kostenentscheide erhob. Es durfte deshalb mangels aktuellem Rechtsschutzinteresse auf die Beschwerde nicht eintreten, ohne Bundesrecht zu verletzen.
Die Beschwerde erweist sich somit als unbegründet und ist abzuweisen, soweit darauf einzutreten ist. Dagegen erschien die Beschwerde nicht als von vornherein aussichtslos, weshalb dem Beschwerdeführer die unentgeltliche Rechtspflege zu gewähren ist und keine Kosten zu erheben sind (<ref-law>). Eine Parteientschädigung kann dem unterliegenden Beschwerdeführer dagegen nicht zugesprochen werden.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Dem Beschwerdeführer wird die unentgeltliche Rechtspflege gewährt. Es werden keine Kosten erhoben.
3. Es werden keine Parteientschädigungen zugesprochen.
4. Dieses Urteil wird dem Beschwerdeführer, der Gemeinde Schwellbrunn, dem Departement Bau und Umwelt sowie dem Verwaltungsgericht von Appenzell Ausserrhoden, 2. Abteilung, schriftlich mitgeteilt.
Lausanne, 14. Oktober 2009
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Féraud Gerber