Sachverhalt: A. Die Staatsanwaltschaft Zürich ermittelt gegen X._ wegen des Verdachts des mehrfachen Betrugs, des mehrfachen betrügerischen Missbrauchs einer Datenverarbeitungsanlage, der mehrfachen Veruntreuung, der mehrfachen Urkundenfälschung sowie der Begünstigung, der Zechprellerei, des Erwerbs und Konsums von Marihuana sowie Verstössen gegen das Strassenverkehrsgesetz. X._ wurde am 5. Juni 2007 verhaftet und am 7. Juni 2007 in Untersuchungshaft versetzt. Am 18. Februar 2009 wurde er aus der Haft entlassen. B. Am 13. Februar 2009 erhob X._ Rekurs bei der Oberstaatsanwaltschaft des Kantons Zürich wegen Verfahrensverschleppung. Am 23. April 2009 wies die Oberstaatsanwaltschaft den Rekurs ab. C. Dagegen hat X._ am 28. Mai 2009 Beschwerde ans Bundesgericht erhoben. Er beantragt, es sei festzustellen, dass eine Verfahrensverzögerung vorliege; die Staatsanwaltschaft Zürich-Sihl sei anzuweisen, das Untersuchungsverfahren gegen ihn ab sofort beförderlich zu führen. Eventualiter seien die Kosten- und Entschädigungsfolgen im vorinstanzlichen Verfahren unter Berücksichtigung des abgewiesenen Nichteintretensantrags der Staatsanwaltschaft angemessen zu korrigieren. Zudem ersucht der Beschwerdeführer um unentgeltliche Verbeiständung. D. Die Oberstaatsanwaltschaft beantragt, auf die Beschwerde sei nicht einzutreten, eventualiter sei sie abzuweisen. Die Staatsanwaltschaft Zürich-Sihl schliesst auf Abweisung der Beschwerde. 