Sachverhalt: A. X._ (geb. 1974) stammt aus Eritrea. Er reiste im November 2007 in die Schweiz ein. Am 11. Januar 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. Seit dem 9. Januar 2013 ist X._ im Besitz der Niederlassungsbewilligung. B. Am 9. Oktober 2010 heiratete X._ in Khartum (Sudan) seine Landsfrau Y._ (geb. 1987). Am 11. Mai 2011 wies das Migrationsamt des Kantons Zürich das Einreise- und Familiennachzugsgesuch der Ehegatten X._ vom 17. Oktober 2010 ab, da X._ seit seiner Einreise in erheblichem Masse (Januar 2010 bis März 2011: Fr. 61'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 11. Mai 2012 bzw. 5. September 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.