Sachverhalt:
A. Am 23. Juli 2010 machte A._ (Beschwerdeführer) beim Arbeitsgericht Zürich gegen die X._ AG (Beschwerdegegnerin) eine arbeitsrechtliche Klage auf Bezahlung von Fr. 95'866.85 nebst Zins anhängig. Mit Urteil vom 5. Mai 2011 wies das Arbeitsgericht die Klage vollumfänglich ab.
Mit Beschluss vom gleichen Datum wies es das Gesuch des Beschwerdeführers um Gewährung der unentgeltlichen Prozessführung und Bestellung eines unentgeltlichen Rechtsbeistandes ab. Den Beschluss versah es mit folgender Rechtsmittelbelehrung:
"Eine Beschwerde gegen diesen Entscheid kann innert 30 Tagen von der Zustellung an im Doppel und unter Beilage dieses Entscheids beim Obergericht des Kantons Zürich, I. Zivilkammer, Postfach 2401, 8021 Zürich, erklärt werden. In der Beschwerdeschrift sind die Anträge zu stellen und zu begründen. Allfällige Urkunden sind mit zweifachem Verzeichnis beizulegen."
Der Beschwerdeführer nahm diesen Beschluss am 12. Mai 2011 in Empfang.
Mit Eingabe vom 14. Juni 2011 erhob er gegen den Beschluss Beschwerde an das Obergericht des Kantons Zürich. Dieses trat mit Beschluss vom 25. Juli 2011 wegen Verspätung nicht auf die Beschwerde ein (Dispositiv-Ziffer 1) und auferlegte dem Beschwerdeführer die Gerichtskosten des Beschwerdeverfahrens mit einer Entscheidgebühr von Fr. 1'000.-- (Dispositiv-Ziffern 2 und 3). Es erwog, der Rechtsvertreter des Beschwerdeführers hätte durch einen Blick in das Gesetz (<ref-law>) und ohne Beizug von Literatur und Rechtsprechung feststellen können, dass gegen prozessleitende Entscheidungen, zu denen die Verweigerung der unentgeltlichen Rechtspflege seit jeher gehöre, innert zehn Tagen Beschwerde zu erheben sei. Er könne sich daher nicht auf berechtigtes Vertrauen in die unzutreffende Rechtsmittelbelehrung des Arbeitsgerichts berufen. Die Beschwerde sei demnach verspätet.
B. Der Beschwerdeführer beantragt mit Beschwerde in Zivilsachen, den Beschluss des Obergerichts aufzuheben. Es sei ihm für das erstinstanzliche Verfahren die unentgeltliche Prozessführung zu bewilligen und in der Person von Rechtsanwalt Urs Bürgin ein unentgeltlicher Rechtsbeistand zu bestellen. Eventualiter sei die Sache zur Anhandnahme der Beschwerde vom 14. Juni 2011 und deren materiellen Beurteilung an das Obergericht zurückzuweisen.
Ausserdem ersucht er für das bundesgerichtliche Verfahren um Bewilligung der unentgeltlichen Rechtspflege und um Bestellung von Rechtsanwalt Urs Bürgin als unentgeltlichen Rechtsbeistand.
Auf die Einholung von Vernehmlassungen wurde verzichtet.

Erwägungen:
1. Angefochten ist ein kantonal letztinstanzlicher Entscheid (<ref-law>), mit dem auf eine Beschwerde gegen die Verweigerung der unentgeltlichen Rechtspflege nicht eingetreten wurde. Dabei handelt es sich um einen Zwischenentscheid, der einen nicht wieder gutzumachenden Nachteil bewirken kann (<ref-law>; <ref-ruling> E. 1.1), unabhängig davon, ob der Entscheid während des Hauptverfahrens mit separater Verfügung oder zusammen mit dem Endentscheid ergangen ist (Urteil 5D_35/2008 vom 16. Juni 2008 E. 1). Nach dem Grundsatz der Einheit des Verfahrens sind Zwischenentscheide mit dem in der Hauptsache zulässigen Rechtsmittel anzufechten (<ref-ruling> E. 3 S. 144). Da der Streitwert der Hauptsache die in arbeitsrechtlichen Streitigkeiten geltende Grenze von Fr. 15'000.-- übersteigt, ist die Beschwerde in Zivilsachen gegeben (<ref-law>).
Wird ein Nichteintretensentscheid angefochten, überprüft das Bundesgericht lediglich, ob die Vorinstanz zu Recht auf das kantonale Rechtsmittel nicht eingetreten ist. Verneint es dies, weist es die Sache an die Vorinstanz zurück, nimmt jedoch nicht selbst eine materielle Beurteilung vor (Urteil 4A_330/2008 vom 27. Januar 2010 E. 2.1 mit Hinweis, nicht publ. in: <ref-ruling>). Demnach kann nur auf das Eventualbegehren auf Rückweisung der Sache an die Vorinstanz eingetreten werden, nicht aber auf den reformatorischen Antrag, es sei dem Beschwerdeführer für das erstinstanzliche Verfahren die unentgeltliche Rechtspflege zu bewilligen.
2. 2.1 Der Beschluss des Arbeitsgerichts vom 5. Mai 2011 wurde am 10. Mai 2011 versandt. Demnach gilt für die Rechtsmittel die Schweizerische Zivilprozessordung (<ref-law>).
Nach <ref-law> kann der Entscheid, mit dem die unentgeltliche Rechtspflege ganz oder teilweise abgelehnt oder entzogen wird, mit Beschwerde angefochten werden. Wird ein im summarischen Verfahren ergangener Entscheid oder eine prozessleitende Verfügung angefochten, so beträgt die Beschwerdefrist 10 Tage, sofern das Gesetz nichts anderes bestimmt (<ref-law>).
Der Entscheid über ein Gesuch um unentgeltliche Rechtspflege ist eine prozessleitende Verfügung im Sinne von <ref-law>. Die Tatsache, dass der Beschluss des Arbeitsgerichts vorliegend am gleichen Datum wie der Entscheid in der Hauptsache gefällt wurde, vermag an dieser Qualifikation nichts zu ändern (vgl. Urteil 5D_35/2008 vom 16. Juni 2008 E. 1.1). Die Rechtsmittelbelehrung des Arbeitsgerichts, das eine Beschwerdefrist von 30 Tagen angab, war demnach unrichtig.
2.2 Aus dem Prinzip von Treu und Glauben (<ref-law>, <ref-law>) ergibt sich, dass den Parteien aus einer unrichtigen Rechtsmittelbelehrung grundsätzlich keine Nachteile erwachsen dürfen (so schon <ref-ruling> E. 2 S. 298 f., 421 E. 2c S. 423 f.). Den erwähnten Schutz kann eine Prozesspartei nur dann beanspruchen, wenn sie sich nach Treu und Glauben auf die fehlerhafte Rechtsmittelbelehrung verlassen durfte. Dies trifft auf denjenigen nicht zu, der die Unrichtigkeit erkannte oder bei gebührender Aufmerksamkeit hätte erkennen müssen. Allerdings vermag nur eine grobe prozessuale Unsorgfalt der betroffenen Partei oder ihres Anwalts eine unrichtige Rechtsmittelbelehrung aufzuwiegen. Rechtssuchende geniessen demnach keinen Vertrauensschutz, wenn der Mangel in der Rechtsmittelbelehrung für sie bzw. ihren Rechtsvertreter allein schon durch Konsultierung der massgebenden Verfahrensbestimmung ersichtlich ist. Dagegen wird nicht verlangt, dass neben den Gesetzestexten auch noch die einschlägige Rechtsprechung oder Literatur nachgeschlagen wird. Wann der Prozesspartei, die sich auf eine unrichtige Rechtsmittelbelehrung verlassen hat, eine als grob zu wertende Unsorgfalt vorzuwerfen ist, beurteilt sich nach den konkreten Umständen und nach ihren Rechtskenntnissen, wobei bei Anwälten naturgemäss ein strengerer Massstab anzulegen ist; von ihnen wird jedenfalls eine "Grobkontrolle" der Rechtsmittelbelehrung verlangt (<ref-ruling> E. 1.2.2.2 S. 376 f.; <ref-ruling> E. 1.3.1 S. 202 f.; <ref-ruling> E. 3.3 S. 134 f.; <ref-ruling> E. 1a/aa S. 258; <ref-ruling> E. 2a S. 422; je mit weiteren Hinweisen).
2.3 Die Vorinstanz erwog, Entscheide betreffend die unentgeltliche Rechtspflege würden seit jeher als prozessleitende Entscheidungen gelten, wozu sie als Belegbeispiele eine ältere Literaturstelle und eine Bestimmung aus dem nicht mehr geltenden Zürcher Zivilprozessrecht anführte (MAX GULDENER, Schweizerisches Zivilprozessrecht, 3. Aufl. 1979, S. 176 Fn. 5 i.V.m. Ziff. 3; § 271 Abs. 1 Ziff. 4 aZPO/ZH). Sie hielt dafür, dem Rechtsanwalt des Beschwerdeführers hätte daher mit Hilfe eines Blickes in die Schweizerische ZPO und ohne Beizug von Literatur und Rechtsprechung klar sein müssen, dass die Rechtsmittelbelehrung des Arbeitsgerichts fehlerhaft sei.
2.4 Der Beschwerdeführer wendet ein, der Verweis auf Literatur von 1979 und auf das nicht mehr geltende Zürcher Zivilprozessrecht stehe in klarem Widerspruch zur Bundesgerichtspraxis, dass die Fehlerhaftigkeit der Rechtsmittelbelehrung ohne Bezug von Literatur und Rechtsprechung erkennbar sein müsse.
Dieser Einwand verkennt, dass die Vorinstanz auf die genannte Literaturstelle und die Regelung der Zürcher ZPO verwies, um zu belegen, dass dem Rechtsanwalt des Beschwerdeführers ohne Weiteres klar sein musste, dass Entscheide betreffend die unentgeltliche Rechtspflege als prozessleitende Verfügungen gelten. Weil dies seit jeher so ist, durfte die Vorinstanz den Wortlaut von <ref-law> als selbstredend betrachten. Sie ging gerade nicht davon aus, dass zum Verständnis von <ref-law> Literatur hätte konsultiert werden müssen. Der gerügte Widerspruch findet sich demnach in den Erwägungen der Vorinstanz nicht.
2.5 Sodann moniert der Beschwerdeführer, der angefochtene Beschluss vernachlässige die übergangsrechtliche Problematik. Der Beschluss des Arbeitsgerichts sei noch aufgrund der Zürcher Zivilprozessordnung erfolgt und sei schon deshalb keine prozessleitende Verfügung im Sinne von <ref-law>.
Der Umstand, dass sich das Verfahren noch nach der Zürcher Zivilprozessordnung abwickelte (<ref-law>), während für die Rechtsmittel bereits die Schweizerische ZPO galt (<ref-law>), ändert nichts daran, dass der Anwalt des Beschwerdeführers die Fehlerhaftigkeit der Rechtsmittelbelehrung bei Anwendung der gebotenen Sorgfalt hätte erkennen können. Denn es war klar, dass sich die Rechtsmittel nach der ZPO richten. An der Qualifikation der Entscheide betreffend unentgeltliche Rechtspflege als prozessleitende Verfügungen änderte sich jedoch mit dem Inkrafttreten der ZPO nichts. Entscheidend ist einzig der Inhalt des genannten Beschlusses. Für die Ermittlung der anwendbaren Rechtsmittelfrist spielte es somit keine Rolle, dass der Beschluss betreffend Verweigerung der unentgeltlichen Rechtspflege nach den Verfahrensbestimmungen der noch anwendbaren Zürcher Zivilprozessordnung erging.
2.6 Unter diesen Umständen bildete die unrichtige Rechtsmittelbelehrung im Beschluss des Arbeitsgerichts keine Vertrauensgrundlage, die ein Eintreten auf die kantonale Beschwerde trotz verpasster Frist hätte rechtfertigen können. Die Beschwerde erweist sich in diesem Punkt als unbegründet.
3. Der Beschwerdeführer rügt sodann eine Verletzung von <ref-law> sowie der Begründungspflicht nach <ref-law>. Er habe in seiner Beschwerde an die Vorinstanz auf <ref-law> hingewiesen, wonach im Verfahren um die unentgeltliche Rechtspflege keine Gerichtskosten erhoben werden. Die Vorinstanz habe trotzdem und ohne jede Begründung eine Entscheidgebühr erhoben und dem Beschwerdeführer die Gerichtskosten auferlegt.
3.1 Ausser bei Bös- oder Mutwilligkeit werden im Verfahren um die unentgeltliche Rechtspflege keine Gerichtskosten erhoben (<ref-law>). Die Frage, ob die Kostenlosigkeit auch in einem allfälligen Beschwerdeverfahren gilt, geht aus dieser Bestimmung nicht explizit hervor.
3.2 Die Vorinstanz auferlegte dem Beschwerdeführer als unterliegender Partei die Gerichtskosten, wobei sie sich auf <ref-law> stützte. Sie begründete nicht ausdrücklich, weshalb sie die in <ref-law> vorgesehene Kostenlosigkeit nicht zur Anwendung brachte. Eine Verletzung der aus dem Gehörsanspruch fliessenden Begründungspflicht ist dennoch nicht gegeben. Der Beschwerdeführer nahm in seiner kantonalen Beschwerde nur sehr vage auf <ref-law> Bezug mit dem Hinweis "soweit das Obergericht im Verfahren um die unentgeltliche Rechtspflege überhaupt Gerichtskosten erhebt (<ref-law>)". Darauf antwortet der angefochtene Beschluss in hinlänglicher Weise: Indem die Vorinstanz ihren Kostenentscheid auf <ref-law> stützte, brachte sie implizite zum Ausdruck, dass sie die Kostenlosigkeit nach <ref-law> in einem allfälligen an das Gesuchsverfahren anschliessenden Beschwerdeverfahren für nicht anwendbar hält.
3.3 Diese Auffassung der Vorinstanz ist denn auch richtig. Wie das Bundesgericht kürzlich entschieden hat, gilt die Kostenlosigkeit nach <ref-law> einzig für das Gesuchsverfahren (vor der ersten oder der zweiten Instanz), nicht jedoch für das Beschwerdeverfahren. Zur Begründung kann auf diesen, zur Publikation vorgesehenen, Entscheid verwiesen werden: BGE 5A_405/2011 vom 27. September 2011 E. 6. Es liegt demnach keine Verletzung von <ref-law> vor.
4. Mit Blick auf die neurechtliche Problematik infolge Inkrafttretens der Schweizerischen ZPO kann nicht gesagt werden, die Begehren des Beschwerdeführers seien von vornherein aussichtslos gewesen. Auch war der Beizug eines Anwalts zur Rechtswahrung notwendig. Dem Gesuch des - bedürftigen - Beschwerdeführers um unentgeltliche Rechtspflege für das bundesgerichtliche Verfahren ist deshalb zu entsprechen (Art. 64 Abs. 1 und 2 BGG). Auf die Erhebung von Kosten wird verzichtet und dem Rechtsvertreter des Beschwerdeführers ein Honorar aus der Bundesgerichtskasse ausgerichtet. Mangels Einholung einer Beschwerdeantwort erwuchs der obsiegenden Beschwerdegegnerin für das bundesgerichtliche Verfahren kein Aufwand, weshalb ihr keine Parteientschädigung zuzusprechen ist.

Demnach erkennt das Bundesgericht:
1. Dem Beschwerdeführer wird für das bundesgerichtliche Verfahren die unentgeltliche Rechtspflege gewährt und es wird ihm Rechtsanwalt Urs Bürgin als Rechtsvertreter beigegeben.
2. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
3. Es werden keine Gerichtskosten erhoben.
4. Rechtsanwalt Urs Bürgin wird aus der Gerichtskasse eine Entschädigung von Fr. 2'000.-- ausgerichtet.
5. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, I. Zivilkammer, schriftlich mitgeteilt.
Lausanne, 1. November 2011
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Klett
Der Gerichtsschreiber: Kölz