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 Art. 62 Abs. 1 BGG 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. 