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.

Erwägungen:
1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten (<ref-law>) kann wegen Rechtsverletzungen gemäss Art. 95 f. BGG erhoben werden. Dabei legt das Bundesgericht seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Es kann eine - für den Ausgang des Verfahrens entscheidende (vgl. <ref-law>) - Sachverhaltsfeststellung von Amtes wegen nur berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder wenn sie auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law>).
2. Die Beschwerde richtet sich sowohl gegen die vorinstanzliche Verneinung eines Rentenanspruchs als auch gegen die Verweigerung beruflicher Massnahmen, wie aus der Beschwerdebegründung hervorgeht (zu deren Heranziehung bei der Interpretation des Rechtsbegehrens: SVR 2004 IV Nr. 25 S. 95 E. 3.2.1 mit Hinweisen, I 138/02). Streitig ist, ob Vorinstanz und Verwaltung die versicherungsmässigen Voraussetzungen der genannten Leistungen zu Recht als nicht erfüllt erachtet haben.
3. 3.1 Im kantonalen Entscheid werden die für schweizerische und ausländische Staatsangehörige mit Wohnsitz und gewöhnlichem Aufenthalt in der Schweiz geltenden versicherungsmässigen und leistungsspezifischen Voraussetzungen des Anspruchs auf (ordentliche und ausserordentliche) Rentenleistungen sowie auf (berufliche) Eingliederungsmassnahmen der Invalidenversicherung zutreffend dargelegt (vgl. Art. 6 Abs. 1 und - hier interessierend - <ref-law> [in Verbindung mit <ref-law>]; Art. 6 Abs. 2 in Verbindung mit <ref-law> [in der bis 31. Dezember 2007 gültig gewesenen, hier anwendbaren Fassung]; <ref-law> in Verbindung mit Art. 42 erster Satz AHVG; Art. 8 in Verbindung mit <ref-law>; <ref-law>). Darauf wird verwiesen.
3. 3.1 Im kantonalen Entscheid werden die für schweizerische und ausländische Staatsangehörige mit Wohnsitz und gewöhnlichem Aufenthalt in der Schweiz geltenden versicherungsmässigen und leistungsspezifischen Voraussetzungen des Anspruchs auf (ordentliche und ausserordentliche) Rentenleistungen sowie auf (berufliche) Eingliederungsmassnahmen der Invalidenversicherung zutreffend dargelegt (vgl. Art. 6 Abs. 1 und - hier interessierend - <ref-law> [in Verbindung mit <ref-law>]; Art. 6 Abs. 2 in Verbindung mit <ref-law> [in der bis 31. Dezember 2007 gültig gewesenen, hier anwendbaren Fassung]; <ref-law> in Verbindung mit Art. 42 erster Satz AHVG; Art. 8 in Verbindung mit <ref-law>; <ref-law>). Darauf wird verwiesen.
3.2 3.2.1 Wie vorinstanzlich ebenfalls richtig dargelegt, ist mit Bezug auf anerkannte Flüchtlinge überdies Art. 24 des Abkommens vom 28. Juli 1951 über die Rechtsstellung der Flüchtlinge (Flüchtlingskonvention, FK; SR 0.142.30) zu beachten (vgl. auch Art. 58 f. AsylG). Dessen Ziff. 1 lautet, soweit hier von Interesse:
1. Die vertragsschliessenden Staaten gewähren den rechtmässig auf ihrem Gebiet sich aufhaltenden Flüchtlingen die gleiche Behandlung wie Einheimischen mit Bezug auf:
a) ...
b) die soziale Sicherheit (gesetzliche Bestimmungen über Arbeitsunfälle, Berufskrankheiten, Mutterschaft, Krankheit, Invalidität, Alter und Todesfall, Arbeitslosigkeit, Familienlasten sowie über alle andern Risiken, die nach der Landesgesetzgebung durch eine umfassende Sozialversicherung gedeckt sind), vorbehältlich:
(i) ...
(ii) der besondern durch die Landesgesetzgebung des Aufenthaltslandes vorgeschriebenen Bestimmungen, die Leistungen oder Teilleistungen ausschliesslich aus öffentlichen Mitteln vorsehen, sowie Zuwendungen an Personen, die die Bedingungen für die Auszahlung einer normalen Rente nicht erfüllen.
Auf diese self-executing-, d.h. innerstaatlich unmittelbar anwendbare Bestimmung können sich Leistungsansprecherinnen und -ansprecher ab dem Datum der Anerkennung als Flüchtling (hier: 22. Juli 2002; vgl. <ref-ruling>), aber nicht rückwirkend, berufen (<ref-ruling> E. 4; siehe auch bereits Urteil des Eidg. Versicherungsgerichts C 162/79 vom 12. November 1980; Jürg Brechbühl, Die Rechtsstellung von Asylsuchenden und Flüchtlingen in den schweizerischen Sozialversicherungen, Soziale Sicherheit 1996 S. 143 ff., 146; Edgar Imhof, Ausländer/innen von ausserhalb der EU/EFTA und Sozialversicherungen - ein Überblick, SZS 2006 S. 433 ff., 451).
3.2.2 Mit Blick auf die Flüchtlingskonvention (E. 3.2.1 hievor) hat der Gesetzgeber gestützt auf Artikel 34quater aBV (heute: <ref-law>) den Bundesbeschluss vom 4. Oktober 1962 über die Rechtsstellung der Flüchtlinge und Staatenlosen in der Alters-, Hinterlassenenversicherung sowie der Invalidenversicherung erlassen [FlüB; SR 831.131.11; hier massgebend in der Fassung gemäss Anhang Ziff. 2 des Bundesgesetzes vom 7. Oktober 1994 [10. AHV-Revision], in Kraft seit 1. Januar 1997 [AS 1996 2466 2488; BBl 1990 II 1]). Art. 1 FlüB sieht vor, dass Flüchtlinge und Staatenlose mit Wohnsitz und gewöhnlichem Aufenthalt in der Schweiz unter den gleichen Voraussetzungen wie Schweizer Bürger Anspruch auf eine ordentliche Rente der Alters- und Hinterlassenen- sowie der Invalidenversicherung haben. Gleiches gilt für ausserordentliche Renten, wenn sich die Flüchtlinge unmittelbar vor dem Zeitpunkt, von welchem an die Rente verlangt wird, ununterbrochen fünf Jahre in der Schweiz aufgehalten haben (Art. 1 Abs. 2 FlüB). Bezüglich des Anspruchs auf Eingliederungsmassnahmen bestimmt Art. 2 FlüB:
1 Erwerbstätige Flüchtlinge mit Wohnsitz und gewöhnlichem Aufenthalt in der Schweiz haben unter den gleichen Voraussetzungen wie Schweizer Bürger Anspruch auf Eingliederungsmassnahmen der Invalidenversicherung, wenn sie unmittelbar vor dem Eintritt der Invalidität Beiträge an die Invalidenversicherung entrichtet haben.
2 Die Nichterwerbstätigen sowie die minderjährigen Kinder mit Wohnsitz und gewöhnlichem Aufenthalt in der Schweiz haben als Flüchtlinge unter den gleichen Voraussetzungen wie Schweizer Bürger Anspruch auf Eingliederungsmassnahmen der Invalidenversicherung, wenn sie sich unmittelbar vor Eintritt der Invalidität ununterbrochen während mindestens eines Jahres in der Schweiz aufgehalten haben. Den minderjährigen Kindern mit Wohnsitz und gewöhnlichem Aufenthalt in der Schweiz steht dieser Anspruch überdies zu, wenn sie in der Schweiz invalid geboren sind oder sich seit der Geburt ununterbrochen in der Schweiz aufgehalten haben.
4. 4.1 Hinsichtlich des umstrittenen Rentenanspruchs hat die Vorinstanz zutreffend geprüft, ob der Beschwerdeführer bei Eintritt der Invalidität während mindestens eines vollen Jahres Beiträge geleistet hat, wie dies auch für Schweizer Bürger verlangt wird (<ref-law> in Verbindung mit Art. 1 Abs. 1 FlüB). Dazu stellte sie fest, der Beschwerdeführer sei bereits bei seiner Einreise in die Schweiz in erheblichem Masse arbeitsunfähig gewesen, was mit überwiegender Wahrscheinlichkeit auf die zwischen 1995 und 1999 in der Türkei erlebte Folter zurückzuführen sei. Der Invaliditätsfall sei daher bei der Einreise in die Schweiz im Jahre 1999 bereits eingetreten gewesen. Die in den Jahren 1990 bis 1994 geleisteten Beiträge könnten nicht anerkannt werden, da diese bei der Rückkehr im Jahre 1994 rückabgewickelt worden seien. Der Beschwerdeführer habe daher die Voraussetzungen gemäss <ref-law> nicht erfüllt.
4.2 Der Beschwerdeführer rügt die vorinstanzliche Sachverhaltsfeststellungen, wonach er bei der (erneuten) Einreise im Jahre 1999 bereits invalid gewesen sei, und wonach die von ihm in den Jahren 1990-1994 geleisteten Beiträge bei der Rückreise 1994 rückabgewickelt worden seien, nach Lage der Akten zu Recht nicht als offensichtlich unrichtig oder als Ergebnis willkürlicher oder sonst rechtsfehlerhafter Beweiswürdigung. Sie sind daher für das Bundesgericht verbindlich (Art. 105 Abs. 1 und 2 BGG).
4.3 Umstritten ist hingegen die Rechtsfrage, ob die in den Jahren 1990-1994 geleisteten Beiträge trotz Rückvergütung gemäss Art. 10a des schweizerisch-türkischen Sozialversicherungsabkommens als "geleistete Beiträge" im Sinne von <ref-law> zu verstehen seien, wie der Beschwerdeführer geltend macht.
4.3.1 Nach dem deutschen und italienischen Wortlaut von <ref-law> ("... Beiträge geleistet haben"; "... hanno pagato i contributi") wäre es nicht ausgeschlossen, die streitigen Beiträge zu berücksichtigen, wurden diese doch seinerzeit "geleistet". Der Sinn der Bestimmung liegt aber offensichtlich darin, dass im Sinne einer Mindestversicherungszeit die Beiträge geleistet und bei der schweizerischen Sozialversicherung noch vorhanden sind; in diese Richtung weist denn auch der französische Wortlaut "compte ... de cotisations". Dafür spricht auch die Analogie zum AHV-Recht, welchem <ref-law> nachgebildet ist (Ulrich Meyer, Rechtsprechung des Bundesgerichts zum Sozialversicherungsrecht, Bundesgesetz über die Invalidenversicherung, Zürich 1997, S. 248 f.): Die Rückvergütung von AHV-Beiträgen bewirkt den Ausschluss eines aus diesen Beiträgen abgeleiteten, anwartschaftlich bestehenden Rentenanspruchs (<ref-law> in Verbindung mit Art. 6 der Verordnung vom 29. November 1995 über die Rückvergütung der von Ausländern an die Alters- und Hinterlassenenversicherung bezahlten Beiträge [RV-AHV; SR 831.131.12]; Urteil des Eidg. Versicherungsgerichts H 48/05 vom 28. Juni 2005 E. 2.1). Diese Konsequenz ergibt sich schliesslich auch klar aus Art. 10a Abs. 2 des schweizerisch-türkischen Sozialversicherungsabkommens (vgl. vorne, lit. A): Danach können türkische Staatsangehörige, deren Beiträge - wie dies beim Beschwerdeführer der Fall war - nach Abs. 1 an die türkische Sozialversicherung überwiesen wurden, gegenüber der schweizerischen AHV und IV aufgrund dieser Beiträge keinerlei Ansprüche mehr geltend machen. Mit der Auszahlung der Beiträge verzichtet der Ausländer definitiv auf entsprechende Leistungen der schweizerischen AHV/IV (Urteil des Eidg. Versicherungsgerichts H 383/00 vom 12. Juli 2001 E. 3c). Diese Regelung ist auch im Ergebnis nicht unbillig; denn die entsprechenden Beiträge werden gemäss Art. 10a Abs. 3 des Abkommens an den zuständigen türkischen Versicherungsträger weitergeleitet und für den Erwerb des Anspruchs auf eine türkische Rente den türkischen Beiträgen und Zeiten gleichgestellt; ergibt sich aus der Überweisung für den Versicherten kein Vorteil aus der türkischen Rentenversicherung, so zahlt der zuständige Träger dem Berechtigten die überwiesenen Beiträge aus. Diese sind somit für den Beschwerdeführer nicht verloren, sondern werden im Sinne einer völkerrechtlich geregelten und damit für das Bundesgericht verbindlichen (<ref-law>) internationalen Koordinationsregelung im Rahmen der türkischen, und nicht mehr der schweizerischen Sozialversicherung berücksichtigt.
4.3.2 Zu prüfen ist, ob die streitigen Beiträge aufgrund von Art. 24 FK (E. 3.2.1 hievor) anzurechnen sind. Wäre der Beschwerdeführer 1994, im Zeitpunkt seiner ersten Ausreise aus der Schweiz, Schweizer Bürger gewesen, hätten die Beiträge weder nach Art. 10a des schweizerisch-türkischen Abkommens noch nach <ref-law> rückvergütet werden können. Sie würden heute als geleistet gelten, so dass die Voraussetzung von <ref-law> erfüllt wäre. Indessen unterstand der Beschwerdeführer bis zu seiner Anerkennung als Flüchtling dem schweizerisch-türkischen Abkommen und erst seither der Flüchtlingskonvention, auf die er sich aber nicht rückwirkend berufen kann (E. 3.2.1 hievor). Er ist somit - aufgrund von Art. 24 FK - gleich zu behandeln, wie wenn er im Zeitpunkt des Erwerbs des Flüchtlingsstatus (22. Juli 2002) das Schweizer Bürgerrecht erhalten hätte. In diesem Falle könnten die vorher der türkischen Sozialversicherung zurückerstatteten Beiträge nicht wieder rückwirkend der schweizerischen AHV gutgeschrieben werden, und sie müssten im Lichte von <ref-law> ausser Betracht bleiben. Würden die Beiträge, wie vom Beschwerdeführer verlangt, berücksichtigt, wäre er (für die Zeit ab seiner Anerkennung als Flüchtling) nicht gleich, sondern besser behandelt als ein Schweizer Bürger in gleicher Lage.
4.3.3 Daraus folgt, dass der Beschwerdeführer aufgrund von <ref-law> keinen Anspruch auf eine ordentliche Rente der Invalidenversicherung hat. Dass der negative Asylentscheid, in dessen Folge der Beschwerdeführer 1994 in die Türkei zurückreiste, nach seiner Auffassung falsch war, ändert daran nichts.
4.4 Zutreffend hat die Vorinstanz sodann erkannt, dass auch kein Anspruch auf eine ausserordentliche Rente der Invalidenversicherung besteht, da der Beschwerdeführer nicht - wie (auch) für die Anspruchsberechtigung von Schweizer Bürgern vorausgesetzt - während der gleichen Zahl von Jahren wie sein Jahrgang versichert war (<ref-law> [in Verbindung mit Art. 24 FK] in Verbindung mit <ref-law>).
5. 5.1 Den ebenfalls strittigen Anspruch auf berufliche Massnahmen hat die Vorinstanz gestützt auf Art. 2 FlüB (E. 3.2.2 hievor) geprüft und ihn - analog zum Rentenanspruch (vgl. E. 4.1 hievor) - mit der Begründung verneint, die leistungsspezifische Invalidität sei bereits vor der Einreise in die Schweiz eingetreten; da der Beschwerdeführer somit unmittelbar vor Eintritt der Invalidität keine Beiträge an die Invalidenversicherung geleistet habe, seien die Leistungsvoraussetzungen gemäss Art. 2 Abs. 1 FlüB nicht erfüllt.
5.2 Der Beschwerdeführer bestreitet (auch diesbezüglich, vgl. vorne E. 4.2) nicht, dass die leistungsspezifische Invalidität vor der Einreise in die Schweiz eingetreten ist. Er macht aber geltend, die in Art. 2 Abs. 1 FlüB statuierte Voraussetzung der Beitragsentrichtung (und des ununterbrochenen, einjährigen Aufenthalts in der Schweiz gemäss Art. 2 Abs. 2 FlüB) unmittelbar vor Invaliditätseintritt stelle eine gegen Art. 24 FK verstossende Ungleichbehandlung von Flüchtlingen gegenüber Schweizer Bürgern dar; die Bestimmung sei daher nicht anwendbar.
5.3 Seit der Aufhebung der Versicherungsklausel in der Invalidenversicherung (Änderung von <ref-law> gemäss Bundesgesetz vom 23. Juni 2000, in Kraft ab 1. Januar 2001, AS 2000 2677; BBl 1999 4983) ist für den Anspruch von Schweizer Bürgern auf Eingliederungsmassnahmen nicht mehr vorausgesetzt, dass sie im Zeitpunkt des Eintritts der leistungsbegründenden Invalidität versichert waren (SVR 2009 IV Nr. 54 S. 168, 9C_1042/2008 E. 4; SVR 2007 IV Nr. 20 S. 70, I 142/04 E. 6.3; Urteil des Eidg. Versicherungsgerichts I 617/00 vom 19. Juni 2001 E. 3). Zu prüfen ist nachfolgend, ob der Beschwerdeführer als anerkannter Flüchtling unmittelbar aus Art. 24 FK (vgl. E. 3.2.1 hievor) einen Anspruch auf diesbezügliche Gleichbehandlung mit Schweizer Bürgern ableiten kann mit der Folge, dass Art. 2 FlüB im Widerspruch zur Flüchtlingskonvention stünde.
5.4 Art. 24 Ziff. 1 lit. b/ii FK erlaubt den Vertragsstaaten, für zwei Kategorien von Leistungen Ausnahmen vom Grundsatz der Inländergleichbehandlung vorzusehen: Einerseits werden genannt (Teil-)Leistungen "ausschliesslich aus öffentlichen Mitteln". Es handelt sich dabei um Leistungen, die nicht mit Versicherungsbeiträgen, sondern aus allgemeinen Mitteln des Staates finanziert werden, wie etwa die Sozialhilfe- oder Fürsorgeleistungen (vgl. Urteil 2P.298/1999 vom 12. April 2000 E. 3). Darunter fallen die Leistungen der Invalidenversicherung mit Ausnahme der Hilflosenentschädigungen nicht (<ref-law>). Andererseits sind vorbehalten "Zuwendungen an Personen, die die Bedingungen für die Auszahlung einer normalen Rente nicht erfüllen". In den massgebenden (vgl. Schlussklausel FK sowie Art. 9 Abs. 2 PublG) französischen und englischen Fassungen lautet die Bestimmung "ainsi que les allocations versées aux personnes qui ne réunissent pas les conditions de cotisation exigées pour l'attribution d'une pension normale" bzw. "and concerning allowances paid to persons who do not fulfil the contribution conditions prescribed for the award of a normal pension". Auf diesen Vorbehalt hat sich die Vorinstanz berufen, unter Hinweis auf das Urteil des Bundesgerichts 8C_295/2008 vom 22. November 2008 E. 5, wonach Art. 2 FlüB auf bundesgesetzlicher Ebene nach innerstaatlichem Recht einen (zulässigen) Vorbehalt im Sinne von Art. 24 Ziff. 1 lit. b/ii FK enthalte. Der Beschwerdeführer bestreitet diese Argumentation.
5.5 Der Beschwerdeführer erfüllt die beitragsmässigen Bedingungen für eine ordentliche Rente nicht (E. 4.1-4.3). Die hier umstrittenen Leistungen fallen damit unter den Wortlaut von Art. 24 Ziff. 1 lit. b/ii FK (vgl. den massgebenden französischen und englischen Wortlaut, woraus klar hervorgeht, dass die beitragsmässigen Voraussetzungen gemeint sind; E. 5.4 hievor). Mit den in Art. 24 Ziff. 1 lit. b/ii FK erwähnten "Zuwendungen" sind zwar in erster Linie diejenigen Leistungen gemeint, die in diesem Falle anstelle einer ordentlichen Rente erbracht werden, wie die altrechtlichen ausserordentlichen Renten der AHV/IV (Imhof, a.a.O., S. 450). Der Wortlaut schliesst aber nicht aus, dass auch für andere Leistungen, namentlich Eingliederungsmassnahmen, an Personen, welche die beitragsmässigen Voraussetzungen nicht erfüllen, die inländische Regelung vorbehalten bleibt.
5.6 Eine den Wortlaut einschränkende Auslegung drängt sich mit Blick auf die Entstehungsgeschichte nicht auf:
5.6.1 Im ursprünglichen Entwurf des Sekretariats des Wirtschafts- und Sozialrats der UNO zur Flüchtlingskonvention war in Art. 16 eine Gleichbehandlung der Flüchtlinge mit den Einheimischen in Bezug auf die Arbeitsgesetzgebung sowie auf die "victims of industrial accidents" vorgesehen gewesen, in Art. 17 eine Gleichbehandlung in Bezug auf soziale Sicherheit, unter Hinweis darauf, dass eine Anzahl internationaler Verträge, namentlich im Rahmen der Internationalen Arbeitsorganisation (IAO), eine Gleichstellung von Ausländern und Staatsangehörigen vorsähen (Ad Hoc Committee on Statelessness and Related Problems, Status of Refugees and Stateless Persons - Memorandum by the Secretary-General 3. Januar 1950, Annex - Preliminary Draft Convention Relating to the Status of Refugees [and Stateless People], zit. nach Alex Takkenberg/Christopher C. Tahbaz, The Collected Travaux préparatoires of the 1951 Geneva Convention relating to the Status of Refugees, Amsterdam 1989, Vol. I, S. 118 ff., 136; vgl. auch http://www.unhcr.org/3ae68c280.html). Die beiden Artikel wurden in der Folge zusammengefasst und in Übereinstimmung mit Art. 6 des am 22. Januar 1952 in Kraft getretenen (von der Schweiz nicht ratifizierten) IAO-Übereinkommens Nr. 97 von 1949 über Wanderarbeiter formuliert (Ad hoc Committee on Statelessness and Related Problems, Summary Record of the Twenty-Third Meeting [3. Februar 1950], zit. nach Takkenberg/Tahbaz, a.a.O., S. 321 ff.; zur Entstehungsgeschichte vgl. auch Cambride International Documents Series Vol. 7: The Refugee Convention 1951, The Travaux Préparatoires Analysed, with a Commentary by the Late Dr. Paul Weis, Cambridge 1995, S. 177 ff.). Damit wurde eine Koordination von Flüchtlings- und allgemeinem Migrationsrecht angestrebt und auf den Umstand Rücksicht genommen, dass viele Staaten gewisse Sozialversicherungsleistungen nicht unterschiedslos den eigenen und ausländischen Staatsangehörigen zukommen lassen. Mit dem Vorbehalt gemäss Art. 24 Ziff. 1 lit. b FK wurde somit bewusst auf eine vollständige Gleichbehandlung der Flüchtlinge mit den Inländern verzichtet. Darüber, welche Leistungen im Einzelnen unter diesen Vorbehalt fallen, geben die Materialien zur Flüchtlingskonvention, soweit ersichtlich, keinen Aufschluss.
5.6.2 Bei der Ratifikation der Flüchtlingskonvention führte der Bundesrat aus, zu Art. 24 müssten Vorbehalte angebracht werden, da das AHVG für Schweizer Bürger praktisch keine Karenzfrist kenne, so dass Flüchtlinge schon nach einem einzigen Beitragsjahr Anspruch auf eine ordentliche Mindestrente der Alters- und Hinterlassenenversicherung hätten (Botschaft vom 9. Juli 1954 zum Beschlussesentwurf über die Genehmigung des Abkommens über die Rechtsstellung der Flüchtlinge vom 28. Juli 1951, BBl 1954 II 78 f.). Die Schweiz fügte deshalb einen (später zurückgezogenen, vgl. Urteil des Eidg. Versicherungsgerichts C 162/79 vom 12. November 1980 E. 2, in: ARV 1981 Nr. 12 S. 53) Vorbehalt zu Art. 24 FK an, wonach der Anspruch auf eine volle ordentliche AHV-Rente eine Mindestaufenthaltsdauer voraussetzte (AS 1955 441 f.). Die später erfolgte Einführung der Invalidenversicherung bot Anlass, das Statut der Flüchtlinge in der Alters-, Hinterlassenen- und Invalidenversicherung zu überprüfen. Resultat dieser Überprüfung war der Erlass des FlüB (vgl. E. 3.2.2 hievor). In der Botschaft dazu führte der Bundesrat aus, eine Ausdehnung des im Bereich der Alters- und Hinterlassenenversicherung angebrachten Vorbehalts auf die Invalidenversicherung sei nicht möglich gewesen, so dass Wege hätten gesucht werden müssen, um eine ungleiche Behandlung der Flüchtlinge in den beiden Versicherungswerken zu vermeiden. In diesem Sinne sei nach Fühlungnahme mit dem Hochkommissar der Vereinten Nationen für Flüchtlinge und den für Flüchtlingsfragen zuständigen schweizerischen Stellen der FlüB ausgearbeitet worden, der davon ausgehe, dass die Schweiz den Vorbehalt zurückziehe. Damit würden die in der Schweiz wohnhaften Flüchtlinge wenigstens in Bezug auf die normalen Renten den Schweizer Bürgern gleichgestellt. Die Flüchtlingskonvention sei indes nicht umfassend, sondern behalte für Leistungen an Flüchtlinge, die die Bedingungen für die Auszahlung einer normalen Rente nicht erfüllten, die Gesetzgebung des Aufenthaltslandes vor; als solche Leistungen hätten die (beitragslosen) ausserordentlichen Renten sowie die Eingliederungsmassnahmen zu gelten (Botschaft vom 19. Januar 1962 zum Entwurf eines Bundesbeschlusses über die Rechtsstellung der Flüchtlinge in der Alters-, Hinterlassenen- und Invalidenversicherung, BBl 1962 I 238 f.). Daher wurden in Art. 2 FlüB die Voraussetzungen für Eingliederungsmassnahmen abweichend von den für Schweizer Bürger geltenden festgesetzt, indem - in Anlehnung an die für ordentliche Renten geltende Regelung - ein Beitragsjahr (bzw. in bestimmten Fällen ein Aufenthaltsjahr) unmittelbar vor Eintritt der Invalidität verlangt wurde.
5.6.3 Daraus ergibt sich, dass mit Art. 2 FlüB nicht etwa eine Abweichung von der Flüchtlingskonvention beabsichtigt war, sondern vielmehr davon ausgegangen wurde, dass die damit eingegangenen völkerrechtlichen Verpflichtungen voll gewahrt wurden (ZAK 1963 S. 102 ff.). Dabei fällt ins Gewicht, dass gemäss den Ausführungen in der Botschaft der FlüB in Abstimmung mit den für Flüchtlinge zuständigen internationalen und nationalen Stellen ausgearbeitet wurde. Hätten diese einen Widerspruch zwischen der Regelung im FlüB und der Flüchtlingskonvention erblickt, wäre dieser zweifellos thematisiert worden.
5.6.4 Im Rahmen der 10. AHV-Revision wurde Art. 2 FlüB dahingehend revidiert, dass für erwerbstätige Flüchtlinge kein Beitragsjahr mehr verlangt wurde, sondern nur noch, dass sie unmittelbar vor dem Eintritt der Invalidität Beiträge an die Invalidenversicherung entrichtet haben. Für nichterwerbstätige Flüchtlinge wurde die einjährige Karenzfrist beibehalten. Diese Regelung bezweckte, die Rechtsstellung der Flüchtlinge der Entwicklung im Bereich der zwischenstaatlichen Sozialversicherungsabkommen anzupassen (Botschaft vom 5. März 1990 über die zehnte Revision der Alters- und Hinterlassenenversicherung, BBl 1990 II 106 f. Ziff. 54), getreu den Verpflichtungen aus Art. 24 Abs. 3 FK, wonach die Vorteile der zwischen den Staaten geschlossenen Abkommen auf die Flüchtlinge auszudehnen sind, ohne aber deren völlige Gleichstellung mit den Einheimischen herzustellen. Auch hier ist nicht ersichtlich, dass seitens der für Flüchtlinge zuständigen Stellen eine Völkerrechtswidrigkeit moniert worden wäre.
5.7 In der Literatur wird die Regelung des FlüB entweder kommentarlos wiedergegeben (Alberto Achermann/Christina Hausammann, Handbuch des Asylrechts, 1991, S. 395; Ueli Kieser, Ausländische Personen und soziale Sicherheit, in: Peter Uebersax et al. [Hrsg.], Ausländerrecht, 2. Aufl. 2009, S. 73 ff., 96 f.; Weis, a.a.O., S. 191) oder bloss rechtspolitisch kritisiert (Ellen Schmid-Winter, Die Rechtsstellung des Flüchtlings, insbesondere in der Sozialversicherung, Diss. Basel 1982, S. 124 ff.), aber nicht etwa als unvereinbar mit der Flüchtlingskonvention betrachtet (unklar Imhof, a.a.O., S. 450 f.). Im Urteil I 551/98 vom 29. Juni 1999 hat denn auch das Eidg. Versicherungsgericht die revidierte Fassung von Art. 2 FlüB angewendet, ohne die Vereinbarkeit mit Art. 24 FK in Frage zu stellen (a.a.O., E. 5 und 6). Auch in dem von der Vorinstanz zitierten Urteil 8C_295/2008 vom 22. November 2008 hat das Bundesgericht, wenn auch bloss obiter, Art. 2 FlüB als eine in Bezug auf Eingliederungsmassnahmen vorbehaltene Bestimmung des Landesrechts im Sinne von Art. 24 Ziff. 1 lit. b/ii FK bezeichnet. Nach dem Gesagten besteht kein triftiger Anlass, von dieser Rechtsprechung abzuweichen.
5.8 Die Vorinstanz hat somit zu Recht auch den Anspruch des Beschwerdeführers auf berufliche Massnahmen verneint.
6. Der unterliegende Beschwerdeführer trägt die Gerichtskosten (Art. 66 Abs. 1). Es kann ihm aber die unentgeltliche Rechtspflege gewährt werden (<ref-law>), unter Hinweis auf die Rückerstattungspflicht nach <ref-law>. Ein Gesuch um unentgeltliche Verbeiständung wurde mit Recht nicht gestellt, da der Rechtsvertreter des Beschwerdeführers nicht Rechtsanwalt ist und deshalb nicht als unentgeltlicher Beistand ernannt werden kann (<ref-ruling> E. 5.1.4 S. 205 f.; <ref-ruling> E. 7.4.1 S. 4).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Die Gerichtskosten von Fr. 500.- werden dem Beschwerdeführer auferlegt, indes infolge Gewährung der unentgeltlichen Rechtspflege vorläufig auf die Gerichtskasse genommen.
3. Dieses Urteil wird den Parteien, dem Verwaltungsgericht des Kantons Bern, Sozialversicherungsrechtliche Abteilung, und dem Bundesamt für Sozialversicherungen schriftlich mitgeteilt.
Luzern, 26. November 2009
Im Namen der II. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Meyer Amstutz