Sachverhalt:
A. Am 11. Juni 2009 erteilte die Baukommission Adliswil der Y._ AG die Baubewilligung für die Erstellung von 5 zusätzlichen Parkplätzen auf dem Grundstück Kat.-Nr. 4934 am Sonnenbergweg 16 in Adliswil.
B. Gegen diesen Beschluss erhob X._ am 24. Juli 2009 Rekurs bei der Baurekurskommission II und beantragte sinngemäss die Aufhebung der Baubewilligung sowie die Wiederherstellung des rechtmässigen Zustands.
Mit Verfügung vom 29. Juli 2009 setzte die Baurekurskommission X._ eine Frist bis zum 10. August 2009, um eine verbesserte Rekursschrift einzureichen und eine Kaution von Fr. 5'000.-- zu leisten, ansonsten auf den Rekurs nicht eingetreten werde.
Nachdem X._ die Kaution innert Frist nicht geleistet hatte, trat die Baurekurskommission am 25. August 2009 auf den Rekurs nicht ein.
C. Dagegen erhob X._ am 4. Oktober 2009 Beschwerde an das Verwaltungsgericht des Kantons Zürich. Er beantragte die Aufhebung der Baubewilligung und ersuchte um Gewährung der unentgeltlichen Rechtspflege.
Am 21. Oktober 2009 wies das Verwaltungsgericht die Beschwerde wie auch das Gesuch um unentgeltliche Rechtspflege ab.
D. Gegen den verwaltungsgerichtlichen Entscheid hat X._ am 4. Januar 2009 Beschwerde an das Bundesgericht erhoben. Er beantragt die Aufhebung des angefochtenen Entscheids und die Rückweisung der Sache an das Verwaltungsgericht mit der Anweisung, das Beschwerdeverfahren materiell an die Hand zu nehmen. Der Beschwerdeführer ersucht um Gewährung der unentgeltlichen Rechtspflege sowie der aufschiebenden Wirkung; als vorsorgliche Massnahme sei der Weiterbau der zusätzlichen Parkplätze zu verbieten.
E. Die Y._ AG beantragt, gestützt auf <ref-law> sei vom Beschwerdeführer die Sicherstellung der Kosten und der Parteientschädigung zu verlangen. In der Sache beantragt sie die Abweisung der Beschwerde. Auch das Verwaltungsgericht schliesst auf Beschwerdeabweisung. Die Baukommission Adliswil hat auf eine Vernehmlassung verzichtet.

Erwägungen:
1. Gegen den angefochtenen Entscheid des Verwaltungsgerichts als kantonal letzte Instanz steht grundsätzlich die Beschwerde in öffentlich-rechtlichen Angelegenheiten offen. Der Beschwerdeführer ist zur Beschwerde legitimiert (<ref-law>). Auf die rechtzeitig erhobene Beschwerde ist grundsätzlich einzutreten, vorbehältlich rechtsgenügend begründeter Rügen (Art. 42 Abs. 2 i.V.m. <ref-law>).
Streitgegenstand des vorinstanzlichen Verfahrens war nur die Frage, ob die Baurekurskommission zu Recht auf den Rekurs des Beschwerdeführers nicht eingetreten ist. Dies bejahte das Verwaltungsgericht, weshalb es die Beschwerde als offensichtlich unbegründet abwies. Ob der Rekurs gegen die Parkplätze in der Sache begründet gewesen wäre, wurde weder von der Baurekurskommission noch vom Verwaltungsgericht geprüft. Diese Frage ist auch nicht Streitgegenstand des bundesgerichtlichen Verfahrens. Soweit der Beschwerdeführer Rügen erhebt, welche die Baubewilligung betreffen, kann darauf nicht eingetreten werden.
2. Der Beschwerdeführer macht zunächst geltend, die Zwischenverfügung vom 29. Juli 2009 sei mit keinem Wort begründet worden und habe keine Rechtsmittelbelehrung enthalten. Insbesondere sei er nicht auf die Möglichkeit hingewiesen worden, gemäss § 16 des Zürcher Verwaltungsrechtspflegegesetzes vom 24. Mai 1959 (VRG) ein Gesuch um unentgeltliche Rechtspflege, d.h. auf Erlass des Kostenvorschusses, zu stellen. Von dieser Möglichkeit habe er keine Kenntnis gehabt.
2.1 Der Beschwerdeführer beruft sich auf § 10 VRG. Danach sind die Behörden verpflichtet, die Erledigung einer Angelegenheit dem Gesuchsteller und den weiteren Verfahrensbeteiligten schriftlich mitzuteilen (Abs. 1); diese Mitteilung ist zu begründen und mit einer Rechtsmittelbelehrung zu versehen, die das zulässige ordentliche Rechtsmittel, die Rechtsmittelinstanz und die Rechtsmittelfrist bezeichnet (Abs. 2).
2.2 § 10 VRG bezieht sich seinem Wortlaut nach nur auf die "Erledigung einer Angelegenheit", d.h. auf Endentscheide. Es erscheint daher fraglich, ob diese Bestimmung überhaupt auf Zwischenentscheide anwendbar ist. Die Frage kann jedoch offen bleiben: Der Beschwerdeführer hat die Kostenvorschussverfügung nicht selbstständig, sondern zusammen mit dem Nichteintretensentscheid der Baurekurskommission angefochten. Diese enthielt eine Begründung, und zwar auch für den zuvor angeordneten Kostenvorschuss, und war mit einer Rechts-mittelbelehrung versehen. Insofern ist nicht ersichtlich, welchen Nachteil der Beschwerdeführer durch die fehlende Begründung und Rechtsmittelbelehrung in der Zwischenverfügung erlitten haben soll.
2.3 Weder aus § 10 VRG noch aus dem Grundsatz des rechtlichen Gehörs (<ref-law>) ergibt sich eine Verpflichtung der Behörden, die Beteiligten eines Verwaltungs- oder Rechtsmittelverfahrens auf die Möglichkeit der unentgeltlichen Rechtspflege aufmerksam zu machen.
Grundsätzlich kann auch von einem juristischen Laien, der zur Zahlung eines Kostenvorschusses aufgefordert wird, erwartet werden, einen Antrag auf unentgeltliche Rechtspflege zu stellen. Hierzu sind keine besonderen juristischen Kenntnisse erforderlich. Es genügt, wenn die Person darlegt, dass sie nicht in der Lage ist, den Kostenvorschuss zu bezahlen, aber an ihrem Gesuch oder Rechtsmittel festhalten will, d.h. um Erlass des Kostenvorschusses bittet.
Im vorliegenden Fall hat der Beschwerdeführer auf die Aufforderung, einen Kostenvorschuss zu zahlen, überhaupt nicht reagiert, obwohl ihm angedroht wurde, dass die Rekurskommission ansonsten auf den Rekurs nicht eintreten würde. Die in derselben Zwischenverfügung enthaltene, gleich lange Frist zur Ergänzung seiner Rekursschrift hat er dagegen eingehalten. Es wäre ihm zuzumuten gewesen, in der ergänzten Rekursschrift wenigstens kurz seine Bedürftigkeit darzulegen und Erlass des Kostenvorschusses zu beantragen.
Nachdem er dies unterliess, war die Baurekurskommission berechtigt, auf den Rekurs - wie angekündigt - nicht einzutreten. Dies verletzte weder das Willkürverbot (<ref-law>), noch den Anspruch auf rechtliches Gehör (<ref-law>), die Rechtsgleichheit (<ref-law>) oder den Anspruch auf ein unparteiisches Gericht (<ref-law>).
3. Der Beschwerdeführer ist ferner der Auffassung, die Voraussetzung zur Erhebung eines Kostenvorschusses gemäss § 15 VRG seien nicht gegeben, da er im öffentlichen Interesse Rekurs erhoben habe; zudem sei seine inhaltliche Einsprache von vornherein evident gewesen, weshalb auch keine Kosten angefallen wären.
3.1 Gemäss § 15 Abs. 2 VRG kann ein Privater unter der Androhung, dass auf sein Begehren sonst nicht eingetreten werde, zur Sicherstellung der Verfahrenskosten angehalten werden, wenn er in der Schweiz keinen Wohnsitz hat (lit. a), wenn er aus einem erledigten und nicht mehr weiterziehbaren Verfahren vor einer zürcherischen Verwaltungs- oder Gerichtsbehörde Kosten schuldet (lit. b) oder wenn er als zahlungsunfähig erscheint (lit. c).
Die Baurekurskommission legte in ihrem Nichteintretensentscheid vom 25. August 2009 dar, dass über den Beschwerdeführer am 29. Juni 2009 der Konkurs eröffnet worden sei, weshalb er als zahlungsunfähig i.S.v. § 15 Abs. 2 lit. c VRG zu betrachten sei. Dies wird vom Beschwerdeführer nicht bestritten.
3.2 Bei der Frage, ob und in welcher Höhe ein Kostenvorschuss erhoben wird, steht der Behörde ein weites Ermessen zu (ALFRED KÖLZ/JÜRG BOSSHART/MARTIN RÖHL, VRG-Kommentar, 2. Aufl., N. 6 zu § 15). Vorliegend gibt es keine Anhaltspunkte dafür, dass das Ermessen missbräuchlich ausgeübt worden ist. Insbesondere ist es nicht willkürlich, den Kostenvorschuss unabhängig von den Erfolgsaussichten des Rechtsmittels und einem allfälligen öffentlichen Interesse aufzuerlegen.
4. Der Beschwerdeführer rügt eine Verletzung des rechtlichen Gehörs im Verfahren vor Verwaltungsgericht. Er ist der Auffassung, das Verwaltungsgericht hätte ihm rückwirkend für das Rekursverfahren die unentgeltliche Rechtspflege gewähren müssen, nachdem er nachträglich ein entsprechendes Gesuch gestellt habe. Damit wäre die Verpflichtung zur Sicherstellung der Verfahrenskosten nachträglich entfallen.
4.1 Gemäss § 16 VRG ist Privaten, welchen die nötigen Mittel fehlen und deren Begehren nicht von vornherein offensichtlich aussichtslos erscheint, auf entsprechendes Ersuchen die Bezahlung von Verfahrenskosten und Kostenvorschüssen zu erlassen. Ein derartiges Gesuch kann grundsätzlich jederzeit während des hängigen Verfahrens gestellt werden. Die Wirkungen treten jedoch erst ab dem Zeitpunkt der Gesuchstellung ein, d.h. es werden nur jene Verfahrens- bzw. Vertretungskosten erfasst, die nach der Stellung des Gesuchs entstehen oder auferlegt werden (Kölz/Bosshart/Röhl, a.a.O., N. 12 zu § 16 VRG). Diese Regelung des kantonalen Rechts entspricht der bundesgerichtlichen Praxis (vgl. Thomas Geiser, in: Basler Kommentar zum BGG, N. 24 zu Art. 64). Die rückwirkende Gewährung von unentgeltlicher Rechtspflege ist auch verfassungsrechtlich in der Regel nicht geboten (vgl. <ref-ruling> E. 2f und 2g S. 208 f.).
4.2 Wird ein Kostenvorschuss, d.h. die Sicherstellung künftiger Verfahrenskosten, verlangt, kann das Gesuch um unentgeltliche Rechtspflege, d.h. auf Erlass des Vorschusses, noch während der laufenden Vorschusszahlungsfrist und selbst nach deren unbenütztem Ablauf gestellt werden, solange das Verfahren noch hängig ist (KÖLZ/BOSSHART/ RÖHL, a.a.O., N. 34 zu § 15).
Im vorliegenden Fall stellte der Beschwerdeführer jedoch den Antrag erst vor Verwaltungsgericht. Zu diesem Zeitpunkt war die Sache nicht mehr bei der Baurekurskommission, sondern beim Verwaltungsgericht hängig, und die unentgeltliche Rechtspflege konnte nur noch für die Kosten des verwaltungsgerichtlichen Verfahrens verlangt werden. Es widerspricht daher weder dem Anspruch auf rechtliches Gehör noch <ref-law>, wenn das Verwaltungsgericht dem Beschwerdeführer nicht nachträglich die unentgeltliche Rechtspflege für das Rekursverfahren gewährte.
5. Schliesslich rügt der Beschwerdeführer, ihm hätte für das Verfahren vor Verwaltungsgericht die unentgeltliche Rechtspflege gewährt werden müssen.
Nachdem die Voraussetzungen von § 15 Abs. 2 lit. c VRG unstreitig vorlagen und der Beschwerdeführer den verlangten Kostenvorschuss nicht rechtzeitig bezahlt hatte, durfte das Verwaltungsgericht die Beschwerde gegen den Nichteintretensentscheid der Baurekurskommission als von vornherein aussichtslos betrachten.
6. Nach dem Gesagten erweist sich auch die Beschwerde vor Bundesgericht als offensichtlich unbegründet. Das Gesuch um unentgeltliche Rechtspflege ist wegen Aussichtslosigkeit abzuweisen (<ref-law>).
Der Beschwerdeführer trägt daher die Kosten des bundesgerichtlichen Verfahrens, die unter Berücksichtigung seiner finanziellen Lage zu bemessen sind (<ref-law>). Praxisgemäss ist der nicht anwaltlich vertretenen Beschwerdegegnerin keine Parteientschädigung zuzusprechen. Unter diesen Umständen konnte auf eine Sicherstellung der Parteientschädigung nach <ref-law> verzichtet werden.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Das Gesuch um unentgeltliche Rechtspflege wird abgewiesen. Die Gerichtskosten von Fr. 500.-- werden dem Beschwerdeführer auferlegt.
3. Es werden keine Parteientschädigungen zugesprochen.
4. Dieses Urteil wird den Parteien, der Baukommission Adliswil und dem Verwaltungsgericht des Kantons Zürich, 1. Abteilung, 1. Kammer, schriftlich mitgeteilt.
Lausanne, 25. Februar 2010
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Féraud Gerber