Sachverhalt: A. A.X._ (geb. 1984) stammt aus Eritrea. Er reiste im Dezember 2007 in die Schweiz ein. Am 26. Januar 2010 gewährte das Bundesamt für Migration ihm Asyl, worauf er im Kanton Graubünden eine Aufenthaltsbewilligung erhielt, welche regelmässig verlängert wurde. Seit dem 22. Januar 2013 verfügt A.X._ über die Niederlassungsbewilligung. B. Am 16. Juni 2011 heiratete A.X._ in Äthiopien seine Landsfrau B.X._ (geb. 1987), die dort ursprünglich in einem Flüchtlingslager lebte und hernach in Addis Abeba eine Stelle als "domestic worker" annahm. Am 15. November 2011 stellte A.X._ ein Gesuch um Familiennachzug, worauf die kantonalen Behörden von ihm einen DNA-Test verlangten (Kosten: Fr. 1'500.--), um einen verwandtschaftlichen bzw. missbräuchlichen Eheschluss ausschliessen zu können. A.X._ stimmte einem solchen grundsätzlich zu. Am 11. Juli 2012 kam in Äthiopien der gemeinsame Sohn des Ehepaars zur Welt. Gleichentags wies das Amt für Polizeiwesen und Zivilrecht des Kantons Graubünden das Nachzugsgesuch von A.X._ ab, da dieser seit seiner Einreise in erheblichem Masse von der Sozialhilfe gelebt habe (per 5. Dezember 2012 für 33 Monate: Fr. 29'275.25), er nicht über die nötigen Mittel verfüge, um den Lebensunterhalt für sich und seine Familie zu bestreiten, und seinem Gesuch "wegen fehlender Überprüfbarkeit" nicht ohne DNA-Test entsprochen werden könne. Am 25. September 2012 ersuchte B.X._ von Äthiopien aus in der Schweiz um Asyl. Mit Entscheiden vom 22. November 2012 bzw. 30. April 2013 bestätigten die kantonalen Rechtsmittelbehörden die Verfügung vom 11. Juli 2012, wobei sie der Frage der Zulässigkeit des DNA-Tests nicht weiter nachgingen. C. A.X._ und B.X._ beantragen vor Bundesgericht, das Urteil des Verwaltungsgerichts des Kantons Graubünden aufzuheben sowie der Gattin und dem gemeinsamen Sohn die Einreise in die Schweiz zu gestatten. Sie ersuchen zudem um unentgeltliche Rechtspflege und Verbeiständung. Die Eheleute machen geltend, der angefochtene Entscheid verstosse gegen Art. 8 EMRK und Art. 13 BV. Ihre privaten Interessen am Familiennachzug überwögen die öffentlichen an dessen Verweigerung; diese erscheine unverhältnismässig, da entgegen der Annahme der Vorinstanz nicht von einer relevanten, absehbar fortdauernden Sozialhilfeabhängigkeit ausgegangen werden könne. Die kantonalen Behörden und das Bundesamt für Migration beantragen, die Beschwerde abzuweisen. A.X._ und B.X._ haben an ihren Anträgen und Ausführungen festgehalten. Sie weisen darauf hin, dass A.X._ inzwischen als Reinigungskraft einen Arbeitsvertrag unterschrieben habe, der ein Bruttoeinkommen von Fr. 3'400.-- vorsehe, zudem habe er eine günstigere Wohnung beziehen können.