Sachverhalt: A. Der 1964 geborene türkische Staatsangehörige B._ reiste 1989 erstmals in die Schweiz ein, wo er von 1990 bis 1994 bei der Firma Z._ AG tätig war. 1994 kehrte er nach Ablehnung seines Asylgesuchs in die Türkei zurück, wobei seine geleisteten AHV/IV/EO-Beiträge gemäss Art. 10a Abs. 1 des Abkommens zwischen der Schweiz und der Republik Türkei über Soziale Sicherheit (SR 0.831.109.763.1) an die türkische Sozialversicherung überwiesen wurden. Am 19. Juli 1999 reiste er erneut in die Schweiz ein. Am 22. Juli 2002 wurde er hier als Flüchtling anerkannt und es wurde ihm Asyl gewährt. Er besitzt die Niederlassungsbewilligung C. Am 29. März 2007 meldete sich B._ bei der Invalidenversicherung zum Leistungsbezug (Umschulung) an. Nach medizinischen Abklärungen und durchgeführtem Vorbescheidverfahren verneinte die IV-Stelle Bern mit Verfügungen vom 20. November 2008 sowohl einen Anspruch auf berufliche Massnahmen als auch einen Rentenanspruch, da die versicherungsmässigen Voraussetzungen nicht erfüllt seien. B. Mit Beschwerde vom 22. Dezember 2008 beantragte B._, die Verfügungen vom 20. November 2008 seien aufzuheben, und es sei die Angelegenheit zur erneuten Prüfung der gesetzlichen Leistungsansprüche an die IV-Stelle zurückzuweisen. Mit Entscheid vom 24. April 2009 wies das Verwaltungsgericht des Kantons Bern die Beschwerde ab. C. B._ lässt Beschwerde in öffentlich-rechtlichen Angelegenheiten erheben mit dem Rechtsbegehren, unter Aufhebung des angefochtenen Entscheids sei die Sache zur ergänzenden Beurteilung der ihm zustehenden Leistungen an die IV-Stelle zurückzuweisen. Ausserdem beantragt er die unentgeltliche Rechtspflege im Sinne der Befreiung von den Gerichtskosten. Die Beschwerdegegnerin schliesst auf Abweisung der Beschwerde, während das Bundesamt für Sozialversicherungen auf eine Vernehmlassung verzichtet. 