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. 