Sachverhalt: A. A._, geboren 1972, stammt aus der Volksrepublik China. Er reiste am 29. September 2002 in die Schweiz ein und ersuchte um Asyl. Am 11. April 2006 zog das Bundesamt für Migration (nachfolgend: BFM) seine Verfügung vom 30. Juni 2004 in Wiedererwägung und nahm A._ als Flüchtling vorläufig auf. A._ war vom 1. November 2005 bis 31. März 2007 als Mitarbeiter im Restaurant K._ angestellt. Am 4. Dezember 2006 bewilligte das BFM seiner Ehefrau und seinen beiden Söhnen (geboren 1997 und 2000) die Einreise in die Schweiz zwecks Familienvereinigung. Diese erfolgte am 19. Januar 2007. Mit Verfügung vom 5. November 2007 lehnte die GastroSocial Ausgleichskasse (nachfolgend: Ausgleichskasse) seinen Anspruch auf Kinderzulagen für die Zeit vom 1. November 2005 bis 18. Januar 2007 ab, sprach ihm hingegen vom 19. Januar bis 31. März 2007 Kinderzulagen zu. B. Mit Entscheid vom 23. April 2008 wies das Verwaltungsgericht des Kantons Bern die hiegegen erhobene Beschwerde ab. C. A._ lässt Beschwerde in öffentlich-rechtlichen Angelegenheiten führen mit dem Antrag, der kantonale Entscheid sei aufzuheben und die Ausgleichskasse sei zu verpflichten, ihm die Kinderzulagen auch für die Zeit vom 1. November 2005 bis 18. Januar 2007 zuzüglich Verzugszins auszurichten. Zudem ersucht er um unentgeltliche Rechtspflege. Die Ausgleichskasse schliesst auf Abweisung der Beschwerde. Das BFM beantragt die teilweise Gutheissung der Beschwerde.