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.

Erwägungen:
1. Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten kann die Verletzung von Bundesrecht gerügt werden (<ref-law>). Soweit sich der angefochtene Entscheid auf Quellen des kantonalen Rechts stützt, welche nicht in Art. 95 lit. c-e BGG genannt werden, beschränkt sich die Überprüfung durch das Bundesgericht demgegenüber thematisch auf die erhobenen und begründeten Rügen (<ref-law>) und inhaltlich auf die Frage, ob die Anwendung des kantonalen Rechts zu einer Bundesrechtswidrigkeit führt. Im Vordergrund steht dabei eine Verletzung verfassungsmässiger Rechte, insbesondere des Willkürverbots nach <ref-law>. Was die Feststellung des Sachverhalts anbelangt, kann gemäss <ref-law> nur gerügt werden, diese sei offensichtlich unrichtig oder beruhe auf einer Rechtsverletzung nach Art. 95 (<ref-ruling> E. 1 S. 95 mit Hinweisen).
2. 2.1 Der Beschwerdeführer macht eine offensichtlich unrichtige Feststellung des Sachverhalts, eine willkürliche Anwendung kantonalen Verfahrensrechts und die Verletzung des rechtlichen Gehörs geltend. Das bei ihm gefundene Geld habe er von N._ zum Kauf eines Ladenlokals/Nagelstudios für sie in Budapest bekommen. Die Vorinstanz habe unter Verletzung der Untersuchungsmaxime die Strafakten nicht beigezogen und N._ nicht als Zeugin vorgeladen.
2.2 Die Vorinstanz wies in ihrem Entscheid unter anderem auf die Auskunfts- und Meldepflicht einer um wirtschaftliche Hilfe ersuchenden Person sowie auf die Mitwirkungspflicht im Verwaltungsverfahren hin. Der Beschwerdeführer habe nicht glaubhaft darlegen können, woher das Geld stamme. Vor den verschiedenen Instanzen seien seine Ausführungen diesbezüglich nicht überzeugend und teilweise widersprüchlich gewesen. Da er den beschlagnahmten Geldbetrag nicht angegeben habe, habe er wirtschaftliche Hilfe unter unwahren oder unvollständigen Angaben im Sinn von § 26 lit. a des Sozialhilfegesetzes des Kantons Zürich vom 14. Juni 1981 (SHG; LS 851.1) erwirkt und sei somit zur Rückerstattung verpflichtet.
3. 3.1 Der Umfang der Untersuchungsmaxime im vorinstanzlichen Verfahren wird durch die kantonalen Verfahrensvorschriften umschrieben (Pra 2004 Nr. 110 S. 613, 5P.376/2003 E. 2.1). Das Bundesgericht prüft deren Auslegung und Anwendung unter dem Gesichtswinkel des Willkürverbots. Willkür liegt nach der Praxis des Bundesgerichtes in der Rechtsanwendung vor, wenn der angefochtene kantonale Entscheid offensichtlich unhaltbar ist, mit der tatsächlichen Situation in klarem Widerspruch steht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft. Das Bundesgericht hebt einen Entscheid jedoch nur auf, wenn nicht bloss die Begründung, sondern auch das Ergebnis unhaltbar ist; dass eine andere Lösung ebenfalls als vertretbar oder gar zutreffender erscheint, genügt nicht (<ref-ruling> E. 4.1 S. 133 mit Hinweisen).
3.2 § 60 des Verwaltungsrechtspflegegesetzes des Kantons Zürich vom 24. Mai 1959 (VRG; LS 175.2) besagt, dass die zur Abklärung des Sachverhaltes erforderlichen Beweise von Amtes wegen erhoben werden. Dieser Grundsatz wird relativiert durch die Mitwirkungspflicht der Parteien (§ 7 Abs. 2 VRG). Für den Bereich der Sozialhilfe wird die Mitwirkungspflicht durch § 18 Abs. 1 SHG konkretisiert, wonach der Hilfesuchende über seine Verhältnisse wahrheitsgemäss Auskunft zu geben und Einsicht in seine Unterlagen zu gewähren hat. Gemäss Kommentierung zu § 60 VRG tragen die Parteien trotz Geltung der Untersuchungsmaxime die Beweislast. Sie sind daher aus praktischen Gründen gezwungen, die ihnen nützlich scheinenden tatsächlichen Behauptungen aufzustellen und entsprechende Beweisbegehren zu stellen. Es ist nicht Aufgabe des Verwaltungsgerichts, systematisch die für die eine oder andere Partei günstigen Tatsachenelemente zu erforschen; der Richter ist in hohem Mass auf die Mitwirkung der Parteien angewiesen. Das Gericht darf daher von der natürlichen Vermutung ausgehen, der Beschwerdeführer habe die für seine Begehren günstigen und die Gegenpartei die für ihn ungünstigen Umstände vorgebracht. Die Untersuchungsmaxime wird im Beschwerdeverfahren zusätzlich dort relativiert, wo das Verwaltungsgericht als zweite Rechtsmittelinstanz wirkt (KÖLZ/BOSSHART/RÖHL, Kommentar zum Verwaltungsrechtspflegegesetz des Kantons Zürich, 2. Aufl. 1999, N. 1 f. zu § 60 VRG).
3.3 Die Vorinstanz wies auf diese Umstände hin und verzichtete auf die Einvernahme von N._ als Zeugin und den Beizug der Strafakten. Der anwaltlich vertretene Beschwerdeführer stellte im vorinstanzlichen Verfahren keinen entsprechenden Beweisantrag. Unter diesen Voraussetzungen lässt der Verzicht auf weitere Massnahmen zur Sachverhaltsabklärung die Anwendung der massgeblichen kantonalen Verfahrensbestimmungen nicht als willkürlich erscheinen. Der Verzicht erweist sich zudem auch im Ergebnis nicht als unhaltbar, wie die nachfolgenden Ausführungen zeigen.
4. 4.1 Die Staatsanwaltschaft hielt in ihrer Einstellungsverfügung vom 17. April 2007 im Zusammenhang mit Drogendelikten fest, obwohl der positive Tatnachweis für eine Beteiligung des Beschwerdeführers am Drogenhandel nicht anklagegenügend habe erstellt werden können, lägen hierfür massgebliche Verdachtsmomente vor. Der Beschwerdeführer habe sich etwa geweigert, den Code für den Tresor, in dem sich ein Teil des Geldes befunden habe, zu nennen, sodass die Polizei diesen habe gewaltsam öffnen müssen. Seine Erklärungsversuche seien wenig plausibel. Insbesondere die in seinem Fingernagelschmutz sichergestellten Kokainspuren und die verhältnismässig grosse Menge sichergestellter Ecstasy-Tabletten belasteten den Beschwerdeführer erheblich. Bei seiner Verhaftung trug der Beschwerdeführer die Summe von Fr. 1'500.- in Stückelung von 30 50er-Noten auf sich. In der Einvernahme durch die Staatsanwaltschaft vom 5. April 2006 konnte er für die im Drogenhandel übliche Stückelung des Geldes keine Erklärung angeben. Nach seinen Angaben habe er mit dem Geldbetrag, den er auf sich trug, "auf den Putz hauen" wollen. Einen Teil des Geldes habe er in der Schuhsole versteckt, damit die Polizei es bei der Verhaftung nicht finde. Auf Nachfragen der Staatsanwaltschaft konnte er sich weder an die Adresse noch an den Namen des potentiellen Verkäufers der Liegenschaft in Budapest genau erinnern. Er führte aus, ihm habe jemand, dessen Name er nicht nennen wolle, ein unbefristetes, unverzinsliches Darlehen von rund Fr. 100'000.- gewährt. Schon seit längerer Zeit habe er für sich eine Wohnung mit Laden in Budapest kaufen wollen. Dies bestätigte er in der Einsprache vom 4. Mai 2007. Dort gab er an, er habe das Geld bekommen, um sich in Ungarn eine Existenzgrundlage aufzubauen. In den späteren Rechtsschriften führte er hingegen aus, das Geld von N._ für den Kauf eines Ladenlokals/Nagelstudios für diese bekommen zu haben. Während des gesamten Verfahrens reichte der Beschwerdeführer, trotz Aufforderung der Behörden, keinen schriftlichen Beleg oder eine Stellungnahme von N._ ein. Wie die Vorinstanz festgestellt hat, vermag der Beschwerdeführer vor diesem Hintergrund keine glaubhafte Erklärung für das bei ihm gefundene Geld zu geben.
4.2 Der von der Vorinstanz ermittelte Sachverhalt kann gestützt auf diese von ihr ausführlich gewürdigten Umstände nicht als offensichtlich unrichtig beurteilt werden. Mit einer Bestätigung durch die Zeugin, wonach das Geld ihr gehörte, wären die aufgezeigten Widersprüche nicht beseitigt. Die Zeugin könnte zu den dargelegten Punkten keine erhellenden Angaben machen, die nicht bereits der Beschwerdeführer im Rahmen seiner Mitwirkungspflicht hätte liefern müssen. Nach Auskunft der Staatsanwaltschaft vom 18. August 2008 verweigerte der Beschwerdeführer im weiteren Strafverfahren die Aussage. Auch Akten über N._ lägen im Strafverfahren keine vor. In antizipierter Beweiswürdigung kann damit auf den Beizug weiterer Strafakten und die Zeugeneinvernahme von N._ verzichtet werden. Weitere Abklärungen würden am massgeblichen Beweisergebnis nichts mehr ändern. Solche Abklärungen wären somit für den Ausgang des Verfahrens auch im Sinne von <ref-law> nicht entscheidend.
5. Der Anspruch auf rechtliches Gehör (<ref-law>) umfasst die Rechte der Parteien auf Teilnahme am Verfahren und auf Einflussnahme auf den Prozess der Entscheidfindung, insbesondere das Recht auf Abnahme der angebotenen Beweismittel unter Vorbehalt einer willkürfreien antizipierten Beweiswürdigung (<ref-ruling> E. 3 S. 157). Der Beschwerdeführer rügt zwar eine Verletzung des rechtlichen Gehörs, legt aber nicht dar, inwiefern die Vorinstanz dieses verletzt hat. Er konnte sich umfassend zur Sache äussern. Sämtliche von ihm im vorinstanzlichen Verfahren offerierten Beweise wurden abgenommen und im Entscheid berücksichtigt.
6. Die Beschwerde ist somit abzuweisen. Bei diesem Verfahrensausgang sind die Gerichtskosten vom Beschwerdeführer als unterliegender Partei zu tragen (<ref-law>). Dem Gesuch um unentgeltliche Rechtspflege (im Sinne der vorläufigen Befreiung von den Gerichtskosten und der unentgeltlichen Rechtsvertretung) kann entsprochen werden, da die entsprechenden Voraussetzungen erfüllt sind (Art. 64 Abs. 1 und 2 BGG; <ref-ruling> E. 4a S. 202). Es wird indessen ausdrücklich auf <ref-law> aufmerksam gemacht, wonach die begünstigte Partei der Gerichtskasse Ersatz zu leisten haben wird, wenn sie später dazu imstande ist.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Dem Beschwerdeführer wird die unentgeltliche Rechtspflege gewährt.
3. Die Gerichtskosten von Fr. 500.- werden dem Beschwerdeführer auferlegt, indes vorläufig auf die Gerichtskasse genommen.
4. Rechtsanwalt Silvan Meier Rhein wird als unentgeltlicher Anwalt des Beschwerdeführers bestellt, und es wird ihm für das bundesgerichtliche Verfahren aus der Gerichtskasse eine Entschädigung von Fr. 2'800.- ausgerichtet.
5. Dieses Urteil wird den Parteien und dem Verwaltungsgericht des Kantons Zürich schriftlich mitgeteilt.
Luzern, 15. Dezember 2009
Im Namen der I. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Ursprung Kathriner