Sachverhalt:
A. B. und A.X._ liessen ihre vier schulpflichtigen Kinder (C._ geb. 1993; D._ geb. 1995; E._ geb. 1997; F._ geb. 1998) an einer Fernschule unterrichten. Am 7. Februar 2005 beschloss der Kantonsrat des Kantons Zürich das neue Volksschulgesetz (VSG; LS 412.100). Die Bestimmungen über Privatschulen und Privatunterricht (§ 68-70) traten auf den 20. August 2007 für das Schuljahr 2007/2008 in Kraft (Ziff. I des Beschlusses des Regierungsrates über die Inkraftsetzung des Volksschulgesetzes vom 20. Juni 2006; LS 412.100.1). Gestützt darauf teilte das Volksschulamt des Kantons Zürich B. und A.X._ am 20. Dezember 2007 mit, dass der bisherige Unterricht an einer Fernschule ab dem Schuljahr 2008/2009 nicht mehr zulässig sei. B. und A.X._ stellten in der Folge ein Gesuch um Ausnahmebewilligung, welches das Volksschulamt mit Verfügung vom 21. April 2008 gestützt auf die fehlende Voraussetzung von § 69 Abs. 3 VSG, wonach der länger als ein Jahr dauernde Privatunterricht nur von einer Person mit abgeschlossener Lehrerausbildung erteilt werden könne, ablehnte. Den dagegen gerichteten Rekurs wies die Bildungsdirektion des Kantons Zürich ab. Auf die nachfolgende Beschwerde trat das Verwaltungsgericht nicht ein und überwies die Sache zum Entscheid an den Regierungsrat, da nicht das Volksschulamt, sondern die Bildungsdirektion zum erstinstanzlichen Entscheid zuständig gewesen wäre.
Am 17. Juli 2008 hatte die Bildungsdirektion B. und A.X._ den Privatunterricht ihrer vier schulpflichtigen Kinder per 15. August 2008 untersagt. Den dagegen gerichteten Rekurs vereinigte der Regierungsrat mit dem bereits hängigen und wies die beiden Rekurse ab. Die nachfolgende Beschwerde an das Verwaltungsgericht war ebenfalls erfolglos mit Ausnahme der Gewährung der unentgeltlichen Rechtspflege. Während des verwaltungsgerichtlichen Verfahrens hat der älteste Sohn die obligatorische Schulpflicht abgeschlossen.
B. Vor Bundesgericht beantragen A. und B.X._ folgendes:
"1. Es sei der Entscheid des Verwaltungsgerichts des Kantons Zürich vom 3. Juni 2010 insoweit aufzuheben, als damit die Verwaltungsgerichtsbeschwerde der Beschwerdeführer vom 8. Februar 2010 gegen den Regierungsratsbeschluss Nr. 2077 vom 23. Dezember 2009 abgewiesen wurde. Ausserdem seien die Verfügungen der Bildungsdirektion des Kantons Zürich vom 7. Juli 2008 und vom 17. Juli 2008 sowie der besagte Regierungsratsbeschluss Nr. 2077 vom 23. Dezember 2009 aufzuheben, der Regierungsratsbeschluss insoweit, als die (vereinigten) Rekurse gegen die besagten Verfügungen der Bildungsdirektion durch den Regierungsrat des Kantons Zürich abgewiesen wurden.
2. Es sei den Beschwerdeführern die Bewilligung zu erteilen, ihre Kinder weiterhin privat zu unterrichten. Eventualiter sei die Sache zum entsprechenden Entscheid an die Vorinstanz zurückzuweisen.
3. Unter Kosten- und Entschädigungsfolge. Eventualiter sei den Beschwerdeführern der Kostenerlass mit dem unterzeichneten Anwalt als unentgeltlicher Rechtsbeistand zu bewilligen."
Schliesslich beantragten die Beschwerdeführer, das bundesgerichtliche Beschwerdeverfahren - vorläufig bis zum 31. Oktober 2010 - zu sistieren.
C. Das Verwaltungsgericht des Kantons Zürich verzichtet auf eine Vernehmlassung. Die Bildungsdirektion und der Regierungsrat des Kantons Zürich beantragen, die Beschwerde abzuweisen.

Erwägungen:
1. 1.1 Die Beschwerde ist innert der gesetzlichen Frist (<ref-law>) eingereicht worden und richtet sich gegen den Entscheid einer letzten kantonalen Instanz (<ref-law>) in einer Angelegenheit des öffentlichen Rechts (<ref-law>). Der Ausschlussgrund nach Art. 83 lit. t BGG ist vorliegend nicht anwendbar. Die Beschwerdeführer sind zur Beschwerde legitimiert (<ref-law>). Auf die Beschwerde ist grundsätzlich einzutreten.
1.2 Die Beschwerdeführer beantragen vor Bundesgericht, den Beschluss des Regierungsrates sowie die Verfügungen der Bildungsdirektion aufzuheben. Darauf ist nicht einzutreten: Vor Bundesgericht sind lediglich Entscheide bundesgerichtlicher Vorinstanzen anfechtbar (<ref-law>), welche die unterinstanzlichen Entscheide ersetzen (sog. Devolutiveffekt); diese gelten indes inhaltlich als mitangefochten (vgl. <ref-ruling> E. 1.4 S. 144).
1.3 Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten kann namentlich eine Verletzung von Bundesrecht, Völkerrecht und kantonalen verfassungsmässigen Rechten gerügt werden (<ref-law>). Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>), doch prüft es, unter Berücksichtigung der allgemeinen Rüge- und Begründungspflicht (Art. 42 Abs. 1 und 2 BGG), nur die geltend gemachten Vorbringen, falls allfällige weitere rechtliche Mängel nicht geradezu offensichtlich sind (<ref-ruling> E. 1.4.1 S. 254). Hinsichtlich der Verletzung von Grundrechten, insbesondere des Willkürverbots, gilt zudem eine qualifizierte Rügepflicht (<ref-law>; vgl. <ref-ruling> E. 4.1 S. 235 mit Hinweisen). Bei der Auslegung und Anwendung des kantonalen Rechts bildet nur das Willkürverbot Prüfmassstab (<ref-ruling> E. 4.2.2 S. 158). Dabei haben die Beschwerdeführer in der Beschwerde im Einzelnen darzulegen (Art. 42 Abs. 2 i.V.m. <ref-law>), inwiefern der angefochtene Entscheid willkürlich sein soll (vgl. <ref-ruling> E. 1 S. 203), d.h. an einem qualifizierten und offensichtlichen Mangel leidet (<ref-ruling> E. 2.2 S. 246; <ref-ruling> E. 1.3 S. 261 mit Hinweisen).
1.4 Das Bundesgericht legt seinem Urteil zudem den von der Vorinstanz festgestellten Sachverhalt zugrunde (<ref-law>), es sei denn, dieser sei offensichtlich unrichtig oder beruhe auf einer Rechtsverletzung im Sinne von <ref-law> (<ref-law>).
1.5 Das Sistierungsgesuch ist infolge Zeitablaufs gegenstandslos geworden.
2. 2.1 Die Privatschulen und der Privatunterricht werden im Kanton Zürich in den § 68 ff. VSG geregelt: Nach § 68 Abs. 1 VSG benötigen Privatschulen, an denen die Schulpflicht erfüllt werden kann, eine Bewilligung der Bildungsdirektion; diese wird erteilt, wenn die dort angebotene Bildung gleichwertig ist wie die Bildung an der öffentlichen Volksschule. Als Privatunterricht gelten der Einzelunterricht und der Unterricht in einer Gruppe bis zu fünf Schülerinnen und Schüler. Die Eltern melden der Gemeinde ihres Wohnortes und der Bildungsdirektion die Umstände des Privatunterrichts, insbesondere die unterrichtende Person, den Stundenplan und die Räumlichkeiten; dauert der Privatunterricht länger als ein Jahr, muss er von einer Person mit abgeschlossener Lehrerausbildung erteilt werden (§ 69 Abs. 2 und 3 VSG). Die Privatschulen und der Privatunterricht werden von der Bildungsdirektion beaufsichtigt; diese kann geeignete Massnahmen treffen, wenn begründete Zweifel bestehen, ob u.a. die Lernziele erreicht werden; bei schwerwiegenden Mängeln kann sie den Privatunterricht untersagen (§ 70 Abs. 1 und 4 VSG). Dauert der Privatunterricht länger als ein Jahr, ist die Qualität des Unterrichts durch die Bildungsdirektion jährlich zu überprüfen (§ 70 Abs. 2 VSG). Nach § 71 VSG stehen u.a. den Schülerinnen und Schülern des Privatunterrichts weitere Leistungen zu, wie etwa der Besuch der Musikschulen am Wohnort oder die Benutzung der Angebote des freiwilligen Schulsports. Konkretisiert werden diese Vorschriften in der Volksschulverordnung vom 28. Juni 2006 (VSV; LS 412.101).
2.2 Zunächst stellt sich die Frage, ob es sich beim vorliegenden Sachverhalt um einen Schulbesuch einer Privatschule oder um Privatunterricht handelt.
Die Kinder der Beschwerdeführer werden an deutschen Fernschulen (je nach Klassenstufe entweder "Deutsche Fernschule" in Wetzlar oder "Institut für Lernsysteme GmbH [ILS]") unterrichtet; sie sind demnach bei diesen Schulen immatrikuliert. Die beiden Schulen sind nach deutschem Recht zugelassen. Das bezeichnende Merkmal des Fernunterrichts besteht darin, dass der Lehrende und der Lernende ausschliesslich oder überwiegend räumlich getrennt sind (siehe dazu § 1 des deutschen Fernunterrichtsschutzgesetzes). Im vorliegenden Fall heisst dies, dass die Lehrer in Deutschland unterrichten und für Fragen (z.B. per Telefon, E-Mail oder Webcam) ansprechbar sind, die Kinder der Beschwerdeführer dagegen an ihrem Wohnort in der Schweiz (d.h. im Kanton Zürich) sind und hier unterrichtet werden (z.B. durch Videoteaching oder Webcam, durch Lesen des bereitgestellten Unterrichtsmaterials) bzw. lernen. Die beiden Fernschulen unterrichten somit im Kanton Zürich. Entsprechend § 68 Abs. 1 VSG bedürften sie einer Bewilligung. Sie besitzen allerdings keine solche und gelten demnach nicht als im Kanton Zürich zugelassene Privatschulen. Die Kinder der Beschwerdeführer besuchen somit keine Privatschule.
2.3 Was die Beschwerdeführer dagegen vorbringen, vermag nicht zu überzeugen:
2.3.1 Sie machen geltend, dass eine Bewilligung gar nicht notwendig wäre und auch nicht dem Konzept einer Fernschule entspräche, in jedem Kanton eine Bewilligung zu verlangen. Vielmehr sei ihre Situation derjenigen gleichzustellen, wo Schweizer Familien ihre Kinder in ausländische, staatlich anerkannte Privatschulen (vornehmlich in Deutschland und Österreich) schickten, welche ebenfalls keiner Bewilligung im Kanton Zürich bedürften.
Die von den Beschwerdeführern behauptete Gleichheit liegt indessen nicht vor. In den aufgeführten Fällen liegt die Schule im Ausland und auch der Unterricht erfolgt dort; d.h. die Kinder besuchen im Ausland die Schule und halten sich während der Unterrichtsdauer nicht im Kanton Zürich auf. Anders ist der hier strittige Fall: Die Kinder halten sich im Kanton Zürich auf, und die Fernschule unterrichtet die Kinder - zwar nicht im Sinne eines Frontalunterrichts, d.h. eines Unterrichts, wo der Lehrer räumlich vor den Lernenden steht - im Kanton Zürich.
2.3.2 Die Beschwerdeführer monieren zudem, dass für ein Verbot der Fernschule keine gesetzliche Grundlage bestünde. Entgegen derer Auffassung verbietet der Kanton Zürich Fernschulen nicht. Er verlangt lediglich für das Führen einer Privatschule, an welcher die Schulpflicht erfüllt werden kann, eine Bewilligung (§ 68 VSG). Dass einer Bewilligungspflicht Art. 15 (Schulfreiheit) der Verfassung des Kantons Zürich vom 27. Februar 2005 [KV ZH; SR 131.211]) entgegen stehen sollte, ist weder dargelegt noch überhaupt ersichtlich.
2.3.3 Inwiefern <ref-law>, die Bilateralen Verträge II zwischen der Europäischen Union und der Schweiz sowie das WTO Vertragswerk daran etwas ändern würden, ist ebenfalls nicht erkennbar, weshalb darauf nicht weiter einzugehen ist. Insoweit bleibt festzuhalten, dass die Kinder der Beschwerdeführer - wie der Kanton Zürich, ohne in Willkür zu verfallen, entscheiden durfte - keine Privatschule besuchen. Wie sich aus den Akten ergibt, stellen selbst die beiden in Deutschland staatlich zugelassenen und zertifizierten Fernschulen nicht eine Ersatzschule für die Regelschule dar. M.a.W. wären die Kinder der Beschwerdeführer auch in Deutschland nicht berechtigt, die Fernschulen anstelle der normalen Schulen (vgl. dazu Art. 7 des deutschen Grundgesetzes) zu besuchen.
3. 3.1 Der Unterricht der Kinder der Beschwerdeführer stellt sich somit als Privatunterricht dar. Da dieser mehr als ein Jahr dauern wird, muss er von einer Person mit abgeschlossener Lehrerausbildung erteilt werden (§ 69 Abs. 3 VSG).
Das Verwaltungsgericht hat festgehalten, dass die Beschwerdeführer über keine genügende Ausbildung verfügen und ihre Kinder deshalb nicht privat unterrichten dürfen. Die Beschwerdeführer machen allerdings geltend, dass zum einen nicht sie, sondern Personen mit abgeschlossener Lehrerausbildung, d.h. die Lehrer der Fernschule, die Kinder fern-unterrichten würden. Zum anderen würde die Auffassung der Vorinstanzen, wonach Privatunterricht nur im Frontalunterricht bestehen könne, dem Grundrecht der Schulfreiheit (Art. 15 KV ZH) widersprechen.
Zunächst soll geprüft werden, ob Fernunterricht als Unterricht zulässig ist. Es stellen sich dabei zwei Fragen: Liegt Privatunterricht zum einen (E. 3.2) und Fernunterricht zum andern (E. 3.3) überhaupt im sachlichen Schutzbereich von Art. 15 KV ZH?
3.2 Das Recht auf Gründung, Organisation und Besuch privater Bildungsstätten ist nach Art. 15 KV ZH gewährleistet. Die Schulfreiheit stellt ein Grundrecht und seiner Struktur nach ein Freiheitsrecht dar; sie begründet Abwehransprüche gegenüber dem Staat. Unter dem Begriff der privaten Bildungsstätten ist auch die Bildung zu Hause, das Homeschooling, enthalten (vgl. Protokoll des Zürcher Verfassungsrates, S. 2929 [Sitzung vom 25.6.2004]; GIOVANNI BIAGGINI, in: Häner und andere (Hrsg.), Kommentar zur Zürcher Kantonsverfassung, 2007, FN 20 ad Art. 15 KV ZH). Privatunterricht ist demnach durch Art. 15 KV ZH geschützt.
3.2 Das Recht auf Gründung, Organisation und Besuch privater Bildungsstätten ist nach Art. 15 KV ZH gewährleistet. Die Schulfreiheit stellt ein Grundrecht und seiner Struktur nach ein Freiheitsrecht dar; sie begründet Abwehransprüche gegenüber dem Staat. Unter dem Begriff der privaten Bildungsstätten ist auch die Bildung zu Hause, das Homeschooling, enthalten (vgl. Protokoll des Zürcher Verfassungsrates, S. 2929 [Sitzung vom 25.6.2004]; GIOVANNI BIAGGINI, in: Häner und andere (Hrsg.), Kommentar zur Zürcher Kantonsverfassung, 2007, FN 20 ad Art. 15 KV ZH). Privatunterricht ist demnach durch Art. 15 KV ZH geschützt.
3.3 3.3.1 Bei der Prüfung der Rüge, wonach Privatunterricht in der Form von Fernunterricht zulässig sein sollte, muss sodann im Auge behalten werden, dass die Regelung des VSG nicht nur den Anforderungen der kantonalen Schulfreiheit, sondern auch den bundesrechtlichen Anforderungen des ausreichenden Grundschul"unterrichts" (Art. 19 i.V.m. <ref-law>) genügen muss. Gleichzeitig wird auch das kantonale Verfassungsrecht der Schulfreiheit bundesrechtlich bestimmt.
Nach den bundesverfassungsrechtlichen Vorgaben hat der private Einzelunterricht ausreichend zu sein. Die Ausbildung muss für den Einzelnen angemessen und geeignet sein sowie genügen, um die Schüler gebührend auf ein selbstverantwortliches Leben im modernen Alltag vorzubereiten (<ref-ruling> E. 7.3 S. 38). Der Anspruch auf ausreichenden Grundschulunterricht wird verletzt, wenn die Ausbildung des Kindes - sei es durch den Staat, sei es durch die Eltern - in einem Masse eingeschränkt wird, dass die Chancengleichheit nicht mehr gewahrt ist bzw. wenn das Kind Lehrinhalte nicht vermittelt erhält, die in der hiesigen Wertordnung als unverzichtbar gelten (<ref-ruling> E. 7.3 i.f. S. 39 mit weiteren Hinweisen), oder es von einer nicht genügend ausgebildeten oder fähigen Lehrperson unterrichtet wird (vgl. ASTRID EPINEY/BERNHARD WALDMANN, § 224 Soziale Grundrechte und soziale Zielsetzungen, in: Merten/Papier/Müller/ Thürer, Handbuch der Grundrechte, Bd. VII/2 Grundrechte in der Schweiz und in Liechtenstein, 2007, S. 611 ff., N. 36 zu § 224), oder dass es in der Gesellschaft oder im demokratischen Gemeinwesen nicht (mehr) partizipieren kann (vgl. PASCAL MAHON, in: Petit commentaire de la Constitution fédérale de la Confédération suisse [...], 2003, Rz. 8 ad art. 19 Cst). Ein ausreichender Grundschulunterricht muss somit nicht nur schulisches Wissen vermitteln, sondern auch die soziale Kompetenz der Schülerinnen und Schüler entwicklungsspezifisch fördern (vgl. dazu auch Art. 1 Abs. 2 der Sportförderungsverordnung vom 21. Oktober 1987 [SFV; SR 415.01]; Urteil 2C_738/2010 vom 24. Mai 2011 E. 3.5.4 und 3.5.6).
3.3.2 Art. 15 KV ZH handelt nur vom Besuch privater Bildungsstätten und nimmt keine Stellung zu den zulässigen Unterrichtsmethoden. Art. 19 und 62 BV führen demgegenüber das Wort "Unterricht"; dabei wird allerdings ebenso wenig Bezug auf eine bestimmte Art von Unterricht genommen. Auch der alltägliche Sprachgebrauch versteht darunter nicht eine besondere Art. Als Unterricht wird die planmässige und regelmässige Unterweisung einer lernenden Person durch eine Lehrerin oder einen Lehrer (vgl. Duden, Das grosse Wörterbuch der deutschen Sprache in sechs Bänden, S. 2709) verstanden; es geht um die Vermittlung von Kenntnissen. Auch die Materialien sowie die Systematik legen keinen Schluss für oder gegen eine bestimmte Unterrichtsform nahe.
Der Zweck der Norm schliesst allerdings gewisse Unterrichtsformen aus, da der Unterricht - wie dargelegt - ausreichend in Bezug auf das schulische Wissen und die soziale Kompetenz sein muss. Beim Privatunterricht steht von seiner Anlage her vor allem das schulische Wissen im Zentrum. Dabei kann der Staat wegen der fehlenden Einbindung des Privatlehrers in das hierarchische Schulsystem und einer fehlenden privaten Institution (Privatschule) die Erreichung der Lernziele der Kinder (vgl. § 70 Abs. 1 VSG) nur über den vorgängig eingereichten Stundenplan, mit der Verpflichtung, eine Person mit abgeschlossener Lehrerausbildung zu beauftragen (vgl. § 69 Abs. 2 und 3 VSG), mit der jährlichen Überprüfung der Qualität des Unterrichts (§ 70 Abs. 2 VSG) und mit dem Verbot des Privatunterrichts bei schwerwiegenden Mängeln (§ 70 Abs. 4 VSG) sicherstellen. Ob dabei der Lehrer frontal oder aus der Ferne unterrichtet, ändert grundsätzlich nichts an dieser Konstellation.
Die entwicklungsspezifische Förderung zur Gemeinschaftsfähigkeit steht beim Privatunterricht dagegen im Hintergrund. Das Bundesgericht hat im Urteil 2C_738/2010 vom 24. Mai 2011 (E. 3.5.5 i.V.m. E. 3.5.6) deshalb festgehalten, dass selbst bei zum Lehrberuf ausgebildeten Eltern notwendigerweise ein ausserfamiliäres und freundschaftsunabhängiges Umfeld einbezogen werden muss, damit eine der Bundesverfassung entsprechende Enkulturation der schulpflichtigen Kinder sichergestellt werde. Diese gewährleistet u.a. eine Auseinandersetzung der Kinder mit anderen Erwachsenen, Vorgesetzten, Respektpersonen, andern Kinder mit teilweise anderen Kulturen und Religionen, was die Kinder schliesslich befähigt, sich im späteren Leben bestmöglich zu integrieren, und ihnen die gleichen Chancen eröffnet. Ob - allenfalls in einem reduzierten Mass - auch bei ausgebildeten Privatlehrern ein ausserfamiliäres und freundschaftsunabhängiges Umfeld in Betracht gezogen werden soll, muss hier nicht beantwortet werden. Beim Fernunterricht erfolgt indes keine direkte Auseinandersetzung zwischen Schüler und Lehrer. Insofern findet überhaupt keine - oder allenfalls nur eine marginale - durch die Schule bzw. durch Lehrer bewirkte entwicklungsspezifische Förderung der sozialen Kompetenz der Schülerinnen und Schüler statt. Es fehlt deshalb bereits an einer von Art. 19 und 62 BV verlangten Grundvoraussetzung.
Zusammenfassend ist festzuhalten, dass Fernunterricht nicht mit Art. 19 und 62 BV und somit auch nicht mit Art. 15 KV ZH vereinbar ist. Ob die Lehrer der Fernschule als ausgebildete Lehrer im Sinne von § 69 Abs. 3 VSG gelten können, muss angesichts dieses Befundes nicht mehr geprüft werden.
3.3.3 Die Beschwerdeführer selber verfügen unbestrittenermassen über keine abgeschlossene Lehrerausbildung, weshalb sie ihre Kinder privat nicht über einen überjährigen Zeitraum unterrichten dürfen (§ 69 Abs. 3 VSG).
4. 4.1 Die Beschwerdeführer machen sodann geltend, dass die Bildungsdirektion im Gesetzgebungsverfahren versprochen hätte, dass der Privatunterricht durch Eltern weiterhin gewährleistet werde. Im Wesentlichen wird damit eine Verletzung des Grundsatzes von Treu und Glauben bei Rechtssetzungsakten gerügt. Die Beschwerdeführer verkennen dabei, dass sie grundsätzlich nicht auf den Fortbestand eines geltenden Erlasses vertrauen können. Eine mögliche Verletzung des Grundsatzes von Treu und Glauben könnte bei unvorhergesehenen Rechtsänderungen vorliegen; in diesen Fällen kann ein Anspruch auf angemessene Übergangsfristen bestehen (zum Ganzen <ref-ruling> E. 7.6. S. 40 f.). Hier hat der Gesetzgeber grosszügige Übergangsfristen vorgesehen. Die Beschwerdeführer setzen sich nicht mit den Argumenten des Verwaltungsgerichts auseinander, inwiefern die Bildungsdirektion, welche nicht Gesetzgeber ist und war, gegen Treu und Glauben vorstossen haben soll; es ist deshalb darauf nicht weiter einzugehen (<ref-law>).
4.2 Inwiefern das Gleichheitsgebot und der Besitzstand verletzt werden, ist ebenfalls nicht ersichtlich. Die Beschwerdeführer setzen sich in keiner Weise mit dem Entscheid des Verwaltungsgerichts auseinander, sondern wiederholen im Wesentlichen die Argumente, die sie bereits vor Vorinstanz vorgebracht haben. Es ist deshalb nicht darauf einzugehen (<ref-law>).
5. 5.1 Die Beschwerde ist abzuweisen, soweit darauf eingetreten werden kann.
5.2 Damit wären die Beschwerdeführer an sich kostenpflichtig (<ref-law>). Da die Beschwerde aber nicht als aussichtslos zu bezeichnen ist und die Bedürftigkeit der Beschwerdeführer als erstellt gelten kann, was das Verwaltungsgericht bereits auch für die vorinstanzlichen Verfahren festgestellt hat, ist dem Gesuch um Gewährung der unentgeltliche Rechtspflege unter Beiordnung des beigezogenen Advokaten zu entsprechen (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Den Beschwerdeführern wird für das Verfahren vor Bundesgericht die unentgeltliche Rechtspflege gewährt:
2.1 Es werden keine Gerichtskosten erhoben.
2.2 Advokat Daniel Albietz wird zum unentgeltlichen Rechtsbeistand bestellt und aus der Bundesgerichtskasse mit Fr. 2'500.-- entschädigt.
3. Dieses Urteil wird den Verfahrensbeteiligten und dem Verwaltungsgericht des Kantons Zürich, 4. Abteilung, 4. Kammer, schriftlich mitgeteilt.
Lausanne, 20. September 2011
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Zünd
Der Gerichtsschreiber: Errass