Sachverhalt: A. Das Bundesamt für Flüchtlinge (heute Bundesamt für Migration) wies das Asylgesuch des 1961 geborenen L._ mit Verfügung vom 19. November 2002 ab; gleichzeitig ordnete es die Wegweisung aus der Schweiz und den Wegweisungsvollzug durch den Kanton St. Gallen an. L._ leistete der Wegweisungsanordnung keine Folge. Der seit November 2009 getrennt von seiner Familie lebende L._ wurde zunächst in S._, Gemeinde X._, untergebracht, wo er Nothilfe bezog. Im Juli 2010 teilte ihn die Koordinationsstelle der St. Galler Gemeinden für Migrationsfragen (KOMI) zum Bezug der Nothilfe nach Y._ um. Mit Eingabe vom 15. Juli 2010 ersuchte L._ das Sozialhilfe- und Vormundschaftsamt Z._ um Ausrichtung von Nothilfe oder um Erlass einer anfechtbaren Verfügung, da es an einer gesetzlichen Grundlage für die erfolgte Zuweisung an eine andere Gemeinde fehle. Am 7. September 2010 reichte er beim Gemeinderat X._ eine Rechtsverweigerungsbeschwerde ein. Mit Entscheid vom 2. November 2010 trat das Sozialhilfe- und Vormundschaftsamt Z._ auf das Nothilfegesuch zufolge örtlicher Unzuständigkeit nicht ein und leitete dieses an die Gemeinde Y._ weiter. Gegen den Nichteintretensentscheid liess L._ Rekurs beim Gemeinderat X._ einlegen. Mit Entscheid vom 3. Dezember 2010 schrieb dieser die Rechtsverweigerungsbeschwerde als gegenstandslos geworden ab und wies gleichzeitig auch den Rekurs ab; dem Begehren um Zusprechung einer ausseramtlichen Entschädigung hat er nicht entsprochen. Dagegen reichte L._ beim Sicherheits- und Justizdepartement des Kantons St. Gallen Rekurs ein. Mit separater Eingabe stellte er zudem ein Ausstandsbegehren gegen die Vorsteherin und den Leiter Rechtsdienst des Departements. Nach Erledigung des Ausstandsverfahrens hiess dieses mit Entscheid vom 23. November 2011 den Rekurs in dem Sinne teilweise gut, als es L._ für das Rechtsverweigerungsverfahren vor dem Gemeinderat X._ eine ausseramtliche Entschädigung von Fr. 100.- zusprach; im Übrigen wies es den Rekurs ab. B. Das Verwaltungsgericht des Kantons St. Gallen wies die dagegen erhobene Beschwerde mit Entscheid vom 23. August 2012 ab (Dispositiv-Ziffer 1). Die Zusprechung ausseramtlicher Kosten lehnte es ebenso ab (Dispositiv-Ziffer 3) wie das Gesuch um unentgeltliche Verbeiständung (Dispositiv-Ziffer 4). C. L._ lässt Beschwerde in öffentlich-rechtlichen Angelegenheiten führen mit den Rechtsbegehren, es seien Dispositiv- Ziffer 1, 3 und 4 des angefochtenen Entscheids und der mitangefochtene Entscheid des Sicherheits- und Justizdepartements des Kantons St. Gallen vom 23. November 2011 aufzuheben, soweit den Rekursanträgen nicht entsprochen worden sei. Eventualiter sei die Sache zu neuer Beurteilung zurückzuweisen mit der Anweisung, die Vorsteherin und der Rechtsdienstleiter des kantonalen Sicherheits- und Justizdepartements hätten in den Ausstand zu treten. Überdies wird um Zusprechung einer höheren Parteientschädigung für die vorinstanzlichen Verfahren und um unentgeltliche Rechtsverbeiständung ersucht. Das kantonale Gericht beantragt die Abweisung der Beschwerde, soweit darauf einzutreten sei. Die Gemeinde X._ verzichtet auf eine Stellungnahme. Mit Eingabe vom 17. Dezember 2012 nimmt L._ nochmals Stellung. D. Der Instruktionsrichter hat beim Rechtsvertreter von L._ eine Beweisauskunft betreffend die in den vorinstanzlichen Eingaben vom 16. April und 9. Mai 2012 erwähnte vorläufige Aufnahme eingeholt. Dieser hat mit Eingabe vom 10. April 2013 den Entscheid des Bundesamtes für Migration vom 6. Januar 2012 über die vorläufige Aufnahme, das Schreiben des Sicherheits- und Justizdepartements des Kantons St. Gallen, Migrationsamt, vom 9. Januar 2012 und das Budget für den Monat März 2013 der Sozialen Dienste St. Gallen eingereicht.