Sachverhalt: A. X._ (geb. 1976) stammt aus Eritrea. Er reiste am 20. September 2008 in die Schweiz ein. Am 21. Mai 2010 gewährte das Bundesamt für Migration ihm Asyl, worauf er im Kanton Zürich eine Aufenthaltsbewilligung erhielt, welche regelmässig verlängert wurde. B. Am 20. Dezember 2010 heiratete X._ im Sudan seine Landsfrau Y._ (geb. 1990), mit der er bereits in der Heimat seit mehreren Jahren eine Beziehung gepflegt haben will. Am 21. September 2011 wies das Migrationsamt des Kantons Zürich das Einreise- und Familiennachzugsgesuch der Ehegatten ab, da X._ seit seiner Einreise in erheblichem Masse (1. Februar 2009 bis 7. September 2011: Fr. 63'000.--) von der Sozialhilfe habe unterstützt werden müssen und er nicht über die nötigen finanziellen Mittel verfüge, um den Lebensunterhalt für sich und seine Frau bestreiten zu können. Die Sicherheitsdirektion und das Verwaltungsgericht des Kantons Zürich bestätigten diese Verfügung auf Rekurs bzw. Beschwerde hin am 3. April 2012 bzw. 22. August 2012. C. X._ und Y._ beantragen vor Bundesgericht, das Urteil des Verwaltungsgerichts aufzuheben und der Gattin die Einreise in die Schweiz zum Verbleib bei ihrem Ehemann zu gestatten; allenfalls sei die Sache zu neuem Entscheid an die kantonalen Instanzen zurückzuweisen. Für das bundesgerichtliche Verfahren sei ihnen die unentgeltliche Rechtspflege und Verbeiständung zu gewähren. Das Verwaltungsgericht des Kantons Zürich hat darauf verzichtet, sich zur Beschwerde zu äussern. Die Sicherheitsdirektion des Kantons Zürich und das Bundesamt für Migration beantragen, die Beschwerde abzuweisen. X._ und Y._ haben an ihren Anträgen und Ausführungen festgehalten. D. Das Bundesgericht hat den Fall an seiner Sitzung vom 5. September 2013 öffentlich beraten.