Sachverhalt: A. F._ bezog von April 2001 bis August 2006 von der Stadt X._ wirtschaftliche Hilfe im Gesamtbetrag von Fr. 170'231.10. Bei einer Hausdurchsuchung am 24. März 2006 fand die Polizei in seiner Wohnung, im Lüftungsraum und in der Parkanlage der Liegenschaft Haschisch, Marihuana, 39 Gramm Crack und rund 160 Tabletten Ecstasy. Sie stellte zudem einen in kleiner Stückelung an verschiedenen Orten in der Wohnung aufbewahrten Bargeldbetrag von Fr. 108'990.- sicher. Am 17. April 2007 verfügte die Staatsanwaltschaft, trotz massgeblicher Verdachtsmomente, die Einstellung der Untersuchung wegen Verbrechens gegen das Betäubungsmittelgesetz. Die Sozialbehörde verpflichtete F._ mit Entscheid vom 29. März 2007, zu Unrecht bezogene Leistungen in der Höhe von Fr. 108'990.-, abzüglich Verfahrenskosten der Staatsanwaltschaft, den Sozialen Diensten zurückzuerstatten. Die erhobene Einsprache, in der geltend gemacht wurde, das Geld gehöre der Drittperson N._ wies die Einspracheinstanz und Geschäftsprüfungskommission der Sozialbehörde mit Entscheid vom 27. August 2007 ab. Der Bezirksrat wies mit Beschluss vom 2. Oktober 2008 den erhobenen Rekurs ebenfalls ab. B. Die hiegegen eingereichte Beschwerde hiess das Verwaltungsgericht des Kantons Zürich mit Entscheid vom 30. April 2009 teilweise gut, indem es F._ die unentgeltliche Verbeiständung im Rekursverfahren gewährte. In Bezug auf die Rückerstattungsforderung wies es die Beschwerde ab. C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten lässt F._ die Aufhebung des vorinstanzlichen Entscheides und den Verzicht auf jede Rückforderung beantragen. Ferner wird um unentgeltliche Prozessführung und Verbeiständung ersucht. Die Sozialbehörde der Stadt X._ und das Verwaltungsgericht des Kantons Zürich schliessen auf Abweisung der Beschwerde.