Sachverhalt:
A. Das Bundesamt für Flüchtlinge (heute Bundesamt für Migration) trat am 3. September 2003 auf das Asylgesuch des aus Algerien stammenden M._ (geb. 1965) und am 7. Juni 2004 auf jenes des aus dem Kongo stammenden A._ (geb. 1971) nicht ein. Gleichzeitig wurden die Betroffenen aufgefordert, das Land umgehend zu verlassen. Sie befolgten die ihnen auferlegte Wegweisung jedoch nicht. Der Migrationsdienst (MIDI) des Amtes für Migration und Personenstand des Kantons Bern (MIP) unterstützte sie in der Folge nur noch im Rahmen der Nothilfe und meldete sie bei der Krankenversicherung ab. Das von M._ am 10. und von A._ am 21. April 2008 gestellte Gesuch um Wiederaufnahme in die obligatorische Krankenversicherung wies das MIP mit Verfügungen vom 29. April 2008 (M._) und vom 6. Mai 2008 (A._) ab, weil der verfassungsmässige Anspruch auf Hilfe in Notlagen weder den Anspruch auf Abschluss einer Krankenversicherung, noch der Bezahlung der Krankenversicherungsprämien durch die Fürsorgebehörde beinhalte. Beide Verfügungsadressaten erhoben dagegen Beschwerde bei der Polizei- und Militärdirektion des Kantons Bern (POM). Diese vereinigte die Verfahren und wies die Beschwerden mit Entscheid vom 2. April 2009 ab.
B. M._ und A._ reichten dagegen Beschwerde ein mit folgenden Rechtsbegehren:
"1. Es sei festzustellen, dass es sich vorliegend um ein Sozialversicherungsverfahren handelt.
2. Der vom MIDI vorgenommene Ausschluss aus der obligatorischen Krankenkasse von A._ und M._ sei zu annulieren.
3. Herr M._ und Herr A._ seien - sofern dies noch nicht geschehen ist - wieder in die obligatorische Krankenversicherung aufzunehmen und dort zu belassen bis sie die Schweiz nachgewiesenermassen verlassen haben oder bis zu ihrem Tod.
4. M._ und A._ seien die medizinischen Leistungen zu entrichten, die aus der obligatorischen Krankenversicherung abzuleiten sind.
5. ...
6. ...".
Das Verwaltungsgericht des Kantons Bern trat mit Entscheid vom 2. November 2009 auf die Beschwerde nicht ein.
C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten lassen M._ und A._ beantragen, der Entscheid des Verwaltungsgerichts sei aufzuheben und sie seien, soweit nicht bereits erfolgt, gegen Krankheit zu versichern. Überdies ersuchen sie um unentgeltliche Rechtspflege.
Das POM und das Verwaltungsgericht schliessen auf Abweisung der Beschwerde, soweit darauf einzutreten ist.

Erwägungen:
1. 1.1 Die Beschwerde richtet sich gegen einen verfahrensabschliessenden Nichteintretensentscheid des Verwaltungsgerichts des Kantons Bern im Bereich des öffentlichen Rechts. Dieser prozessuale Endentscheid bildet ein zulässiges Anfechtungsobjekt der Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht (Art. 82 lit. a i.V.m. Art. 86 Abs. 1 lit. d und Art. 90 BGG). Ein Ausschlussgrund nach <ref-law> liegt nicht vor.
1.2 Nach den unbestrittenen Feststellungen des Verwaltungsgerichts wurde der Beschwerdeführer 2 durch den MIDI auf den 1. September 2008 wieder bei einer Krankenversicherung angemeldet. Er begründet seine Beschwerdelegitimation nicht (Art. 42 Abs. 1 und 2 BGG). Da auch sonstwie nicht ersichtlich ist, inwiefern er durch den vorinstanzlichen Entscheid beschwert wäre, ist auf seine Beschwerde nicht einzutreten.
1.3 Der Beschwerdeführer 1, welcher seit der vom MIDI auf den 31. August 2004 erfolgten Abmeldung keiner Krankenkasse mehr angeschlossen ist, verlangt die Wiederaufnahme in die obligatorische Krankenversicherung. Er hat am vorinstanzlichen Verfahren teilgenommen und macht geltend, das Verwaltungsgericht habe durch den Nichteintretensentscheid den Anspruch auf gerichtliche Beurteilung verletzt. Zu dieser Rüge ist er im bundesgerichtlichen Verfahren berechtigt (<ref-law>). Der Streitgegenstand ist jedoch auf diese Frage beschränkt. Deshalb kann insofern nicht auf die Beschwerde eingetreten werden, als der Beschwerdeführer 1 geltend macht, er sei obligatorisch gegen Krankheit zu versichern. Hat die Beschwerde Erfolg, führt dies zur Aufhebung des angefochtenen Entscheids und zur Rückweisung der Sache an das Verwaltungsgericht zu materieller Beurteilung der Streitsache.
2. 2.1 Das kantonale Gericht ging davon aus, dass MIP und POM das Gesuch des Beschwerdeführers 1 vom 10. April 2008 um Wiederaufnahme in die obligatorische Krankenversicherung als Gesuch um Abschluss einer Krankenversicherung zu seinen Gunsten und auf Kosten des Amtes entgegengenommen haben. Sie hätten dieses abgewiesen, weil zum einen die kantonalen Nothilfeleistungen lediglich die medizinische Notfallversorgung umfassen würden, nicht aber die Finanzierung von Krankenkassenprämien und sich zum andern aus dem Versicherungsobligatorium nach KVG kein Leistungsanspruch gegenüber dem MIP ableiten lasse. Somit sei nur über die Frage der Finanzierung der Krankenkassenprämien im Rahmen der kantonalen Nothilfe und nicht über die sozialversicherungsrechtliche Versicherungspflicht nach KVG entschieden worden. Nach Auffassung des Verwaltungsgerichts war dieses Vorgehen mit Blick auf die gesetzliche Zuständigkeitsordnung korrekt, da weder dem MIP noch dem POM auf dem Gebiet der obligatorischen Krankenversicherung eine Verfügungs- bzw. Entscheidbefugnis zustehe. Das MIP könne im Zusammenhang mit der medizinischen Versorgung von Personen mit asylrechtlicher Wegweisung und abgelaufener Ausreisefrist lediglich über den Zugang zur Nothilfe und die unter diesem Titel zu erbringenden Leistungen befinden. Da es dem Beschwerdeführer erklärtermassen nicht um die Frage der Finanzierung der Krankenkassenprämien durch den MIDI gehe, die Sozialhilfebehörde für die Beurteilung der streitigen Versicherungspflicht gemäss KVG jedoch nicht zuständig sei, trat die Vorinstanz auf die Beschwerde nicht ein.
2.2 Der Beschwerdeführer 1 rügt das vorinstanzliche Nichteintreten als formelle Rechtsverweigerung (<ref-law>). Er macht geltend, das kantonale Gericht habe sich nicht mit der beanstandeten Bundesrechtswidrigkeit der Bestimmungen des Kantons Bern auseinandergesetzt, welche Ausländer im Besitze eines vollstreckbaren Wegweisungsentscheids von der obligatorischen Krankenversicherung ausschliessen würden. In diesem Zusammenhang rügt er eine Verletzung von <ref-law> (Menschenwürde) und <ref-law> (Recht auf Hilfe in Notlagen) sowie von Art. 3, Art. 6 und Art. 7 KVG und von Art. 82 und Art. 82a des Asylgesetzes vom 26. Juni 1998 (AsylG; SR 142.31).
2.3 Eine formelle Rechtsverweigerung liegt nach der Praxis des Bundesgerichts vor, wenn eine Behörde auf eine ihr frist- und formgerecht unterbreitete Sache nicht eintritt, obschon sie darüber befinden müsste. Ob eine Rechtsverweigerung vorliegt, prüft das Bundesgericht frei. Die Auslegung und Anwendung des einschlägigen kantonalen Rechts untersucht es hingegen nur unter dem Gesichtswinkel der Willkür (<ref-ruling> E. 2.1 S. 9 mit Hinweis).
2.4 Nach der Rechtsprechung (vgl. <ref-ruling> E. 2 S. 415, mit Hinweisen) bilden Anfechtungsgegenstand in der nachträglichen Verwaltungsrechtspflege formell betrachtet Verfügungen und materiell betrachtet die in Verfügungen geregelten Rechtsverhältnisse. Die begriffliche Unterscheidung von Streit- und Anfechtungsgegenstand erfolgt danach auf der Ebene von Rechtsverhältnissen.
2.5 Die soziale Krankenversicherung ist im KVG geregelt. Dieses bestimmt, wer obligatorisch für Krankenpflege zu versichern ist (vgl. <ref-law> und <ref-law>). Die Kantone sorgen nach <ref-law> für die Einhaltung der Versicherungspflicht (Abs. 1). Die vom Kanton bezeichnete Behörde weist Personen, die ihrer Versicherungspflicht nicht rechtzeitig nachkommen, einem Versicherer zu (Abs. 2). Im Kanton Bern sorgt das Amt für Sozialversicherung und Stiftungsaufsicht (ASVS) für die Einhaltung der Versicherungspflicht (Art. 1 Abs. 1 des Gesetztes des Kantons Bern vom 6. Juni 2000 betreffend die Einführung des Bundesgesetzes über die Kranken-, die Unfall- und die Militärversicherung [EG KUMV; BSG 842.11] in Verbindung mit Art. 16 lit. d der Verordnung des Regierungsrates des Kantons Bern vom 18. Oktober 1995 über die Organisation und die Aufgaben der Justiz-, Gemeinde- und Kirchendirektion [Organisationsverordnung JGK, OrV JGK; BSG 152.221.131] und Art. 2 Abs. 2 und Abs. 3 der kantonalen Krankenversicherungsverordnung vom 25. Oktober 2000 [KKVV; BSG 842.111.1]).
2.6 Wie das kantonale Gericht erwogen hat, konnte die seinerzeitige "Abmeldung von der Krankenversicherung" durch den MIDI einzig die Einstellung ihrer Prämienfinanzierung für den Beschwerdeführer zur Folge haben. Über den Ausschluss aus der obligatorischen Krankenversicherung konnte dagegen nur der zuständige Krankenversicherer befinden. Dasselbe gilt auch hinsichtlich der streitigen Wiederaufnahme. Dieser hat darüber zu befinden, wer die Anmeldung vornehmen und in die obligatorische Versicherung aufgenommen werden kann. Indem das kantonale Gericht im angefochtenen Entscheid davon ausging, die Sozialhilfebehörden des Kantons Bern seien bezüglich der beantragten Wiederaufnahme in die sozialversicherungsrechtliche Krankenversicherung nicht verfügungsberechtigt, verstösst dies nicht gegen Bundesrecht.
2.7 MIP und POM haben denn auch gar nicht über die Wiederaufnahme in die Versicherung gemäss KVG befunden, sondern den Beschwerdeführer diesbezüglich sinngemäss an den Krankenversicherer verwiesen. Mangels Zuständigkeit der Sozialhilfebehörde hätten sie diesen Punkt auch gar nicht zum Anfechtungsgegenstand erheben können. Hinsichtlich der vom Beschwerdeführer einzig zum Prozessthema erklärten Versicherungspflicht nach KVG fehlt es an einem anfechtbaren Entscheid der sachlich zuständigen Behörde.
2.8 Nach dem Gesagten stellt der angefochtene Nichteintretensentscheid keine unzulässige Rechtsverweigerung dar. Der Beschwerdeführer hat weiterhin die Möglichkeit, sich an einen Krankenversicherer zu wenden und von diesem gegebenenfalls eine anfechtbare Verfügung zu verlangen, oder er kann das ASVS um Zuweisung zu einem Versicherer ersuchen. Seine auf die Versicherungspflicht abzielenden Rügen wird er in jenem Verfahren erneut vorbringen können.
3. Die Beschwerde des Beschwerdeführers 1 ist somit abzuweisen, soweit darauf einzutreten ist, während auf die Beschwerde des Beschwerdeführers 2 nicht einzutreten ist. Dem Ausgang des Verfahrens entsprechend sind die Gerichtskosten grundsätzlich den Beschwerdeführern als unterliegende Partei aufzuerlegen (<ref-law>). Sie haben indessen um unentgeltliche Rechtspflege ersucht. Da die Voraussetzungen von <ref-law> erfüllt sind, kann ihrem Gesuch entsprochen werden. Ihr Rechtsvertreter ist aus der Gerichtskasse angemessen zu entschädigen. Es wird indessen ausdrücklich auf <ref-law> hingewiesen, wonach die begünstigte Partei der Gerichtskasse Ersatz zu leisten hat, wenn sie später dazu in der Lage ist.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde des Beschwerdeführers 1 wird abgewiesen, soweit darauf einzutreten ist.
2. Auf die Beschwerde des Beschwerdeführers 2 wird nicht eingetreten.
3. Den Beschwerdeführern wird die unentgeltliche Rechtspflege gewährt.
4. Die Gerichtskosten von insgesamt Fr. 500.- werden den Beschwerdeführern auferlegt, indes vorläufig auf die Gerichtskasse genommen.
5. Advokat François Couchepin wird als unentgeltlicher Anwalt bestellt, und es wird ihm für das bundesgerichtliche Verfahren aus der Gerichtskasse eine Entschädigung von Fr. 2'800.- ausgerichtet.
6. Dieses Urteil wird den Parteien und dem Verwaltungsgericht des Kantons Bern schriftlich mitgeteilt.
Luzern, 22. Dezember 2010
Im Namen der I. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Ursprung Hofer