Faits: A. A.a. B._, ressortissant serbe, a annoncé son entrée en Suisse au mois de juillet 1998 dans le canton X._, où il a déposé une demande d'asile. Par décision du 18 septembre 1998, l'Office fédéral des réfugiés (ODR), actuellement l'Office fédéral des migrations (ODM), a refusé d'entrer en matière sur sa demande et a ordonné son renvoi. Le prénommé serait en réalité arrivé en Suisse et y aurait travaillé sans autorisation depuis octobre 1994. B._ a été victime d'un accident professionnel le 12 janvier 1999, alors qu'il travaillait au service d'un atelier de mécanique dans le canton Y._. Il a été mis au bénéfice d'une admission provisoire par l'ODR le 23 juin 2004, au motif que l'exécution d'un renvoi l'exposerait à une mise en danger concrète au regard de son état de santé, de sorte qu'elle ne pouvait pas être exigée. A._, qu'il a épousée en avril 2006, est admise à titre provisoire depuis le 18 mai 2006. Le couple a deux enfants. A.b. Par décision du 23 novembre 2000, la Caisse nationale suisse d'assurance en cas d'accidents (CNA), qui avait pris en charge les conséquences de l'accident du 12 janvier 1999, a mis fin au versement de l'indemnité journalière à compter du 3 décembre 2000. A l'issue de différentes procédures, la CNA a par la suite pris les décisions suivantes: - Dans un premier temps, elle a fixé à 20 % le taux de l'incapacité de travail, pour la période du 4 décembre 2000 à fin février 2006, ce qui impliquait un versement rétroactif à l'assuré de 32'893 fr. 25, payé en mars 2006. - Dans un deuxième temps, elle a reconnu rétroactivement à l'assuré une incapacité totale de travail depuis le 4 décembre 2000. En janvier 2007, elle a versé en mains de l'assuré, au titre d'indemnités journalières arriérées, un solde de 147'107 fr. 15. - Elle a mis fin aux indemnités journalières versées à l'intéressé au 31 décembre 2007 et, par décision du 7 janvier 2008, elle l'a mis au bénéfice d'une rente d'invalidité fondée sur une incapacité de gain de 100 % à partir du 1 er janvier 2008. Elle lui a en outre alloué une indemnité pour atteinte à l'intégrité de 35 % (soit 34'020 fr.). - Enfin, elle a versé à l'assuré, le 2 octobre 2007, des intérêts moratoires à hauteur de 38'243 fr. 15. A.c. A la suite de l'attribution de B._ au canton de Vaud par les autorités d'asile, la Fondation vaudoise pour l'accueil des requérants d'asile (ci-après: la FAREAS), actuellement l'Etablissement vaudois d'accueil des migrants (ci-après: l'EVAM), l'a mis au bénéfice de prestations d'aide sociale à partir du 1 er août 2003. Par décision du 13 avril 2007, confirmée sur opposition le 22 juin 2007, la FAREAS a réclamé à B._ la restitution d'un montant de 62'581 fr. 85 pour les prestations d'aide sociale versées entre le 1 er août 2003 et le 28 février 2007. Cette décision était motivée par le fait que l'intéressé avait perçu pendant la période en cause et à titre rétroactif des pleines indemnités journalières de l'assurance-accidents. Saisi d'un recours de B._ et A._ contre la décision précitée du 22 juin 2007, le chef du Département de l'intérieur l'a rejeté par décision du 17 janvier 2011. A.d. A._ et B._ ont déféré cette décision à la Cour de droit administratif et public du Tribunal cantonal vaudois. Ils ont conclu à l'annulation de la décision attaquée et demandé au tribunal de dire que la créance en remboursement de 62'581 fr. 85 était prescrite. Subsidiairement, ils ont conclu à une remise de l'obligation de rembourser. La juridiction cantonale a statué le 30 mai 2012. Sur recours des époux, le Tribunal fédéral a annulé l'arrêt attaqué et a renvoyé la cause à l'autorité cantonale pour qu'elle donne suite à la requête de débats publics qui avait été présentée devant elle par les recourants (arrêt 8C_522/2012). B. La Cour de droit administratif et public a tenu une audience le 11 décembre 2012. Par arrêt du 27 décembre 2012, elle a rejeté le recours. C. Contre ce jugement, A._ et B._ exercent un recours en matière de droit public dans lequel ils concluent à l'annulation du jugement attaqué et à la suppression, pour cause de prescription, de l'obligation de rembourser le montant de 62'581 fr. 85 (ch. 1 et 2). Ils concluent au versement d'indemnités de dépens pour une procédure de recours contre une décision sur opposition de la FAREAS du 16 novembre 2007 (chiffre 3), pour la procédure devant l'EVAM et le Département (chiffre 4) et pour la procédure devant le tribunal cantonal (chiffre 5). Ils demandent en outre à être mis au bénéfice de l'assistance judiciaire pour la procédure fédérale. L'EVAM s'en remet à la décision attaquée. L'ODM s'est déterminé par courrier du 25 avril 2013. 