Sachverhalt:
A. X._, geb. 3. März 1991, stammt nach eigenen Angaben aus Bangladesch. Er reiste am 25. Juli 2002 zusammen mit seiner Mutter und seinem Bruder illegal in die Schweiz ein und stellte am Folgetag ein Asylgesuch. Das Bundesamt für Migration (BFM) lehnte dieses am 3. Mai 2004 ab und wies sowohl X._ als auch dessen Mutter und Bruder aus der Schweiz weg. Es setzte ihnen für die Ausreise aus der Schweiz Frist bis zum 28. Juni 2004. Die gegen diese Verfügung erhobenen Rechtsmittel blieben erfolglos. X._ hat die Schweiz bis heute nicht verlassen.
Am 13. Oktober 2008 wurde X._ vom Migrationsdienst des Kantons Bern in Ausschaffungshaft genommen. Mit Entscheid vom 15. Oktober 2008 bestätigte das Haftgericht III Bern-Mittelland die Anordnung der Ausschaffungshaft für die Zeit bis zum 12. Januar 2009.
B. Gegen den Entscheid des Haftgerichts III Bern-Mittelland führt X._ mit Eingabe vom 29. Oktober 2008 Beschwerde in öffentlich-rechtlichen Angelegenheiten. Er beantragt, es sei der angefochtene Entscheid aufzuheben und er sei aus der Ausschaffungshaft zu entlassen. Am 17. November 2008 reichte der Beschwerdeführer eine ergänzende Eingabe ein.
Das Haftgericht III Bern-Mittelland und der Migrationsdienst des Kantons Bern schliessen auf Abweisung der Beschwerde. Das BFM verzichtet in seiner Vernehmlassung auf einen Antrag.

Erwägungen:
1. 1.1 Auf die Beschwerde kann eingetreten werden, da sie unter Einhaltung der gesetzlichen Frist (<ref-law>) und Form (<ref-law>) von einer durch die Entscheidung besonders berührten Partei mit einem schutzwürdigen Interesse an deren Aufhebung oder Änderung (<ref-law>) eingereicht wurde. Sie richtet sich gegen einen von einer letzten kantonalen Instanz (<ref-law>) gefällten Endentscheid (<ref-law>) in einer Angelegenheit des öffentlichen Rechts (<ref-law>). Keine der in <ref-law> erwähnten Ausnahmen ist anwendbar.
1.2 Die Beschwerde kann wegen Rechtsverletzung gemäss Art. 95 und Art. 96 BGG erhoben werden. Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>). Es ist somit weder an die in der Beschwerde geltend gemachten Argumente noch an die Erwägungen der Vorinstanz gebunden; es kann eine Beschwerde aus einem anderen als dem angerufenen Grund gutheissen und es kann eine Beschwerde mit einer von der Argumentation der Vorinstanz abweichenden Begründung abweisen.
1.3 Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Es kann die Sachverhaltsfeststellung der Vorinstanz nur berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law>). Der Beschwerdeführer, welcher die Sachverhaltsfeststellungen der Vorinstanz anfechten will, muss substantiiert darlegen, inwiefern die qualifizierten Voraussetzungen gemäss <ref-law> gegeben sind. Andernfalls kann ein von dem im angefochtenen Entscheid festgestellten abweichender Sachverhalt nicht berücksichtigt werden (vgl. <ref-ruling> E. 1.4 S. 140).
2. 2.1 Zu prüfen ist, ob das Haftgericht III Bern-Mittelland die Voraussetzungen für die Anordnung der Ausschaffungshaft zu Recht bejaht hat. Im angefochtenen Entscheid führt die Vorinstanz aus, es bestehe beim Beschwerdeführer Untertauchensgefahr. Sie begründet dies im Wesentlichen damit, dass dieser einerseits falsche Angaben zu seiner Nationalität gemacht habe, und andererseits auch der Verdacht bestehe, der Beschwerdeführer handle mit Betäubungsmitteln. Zudem sei er mittel- und obdachlos und habe auch zu erkennen gegeben, dass er nicht zurück in sein Heimatland wolle. Der Beschwerdeführer bestreitet diese Vorhalte vollumfänglich.
2.2 Wurde ein erstinstanzlicher Weg- oder Ausweisungsentscheid eröffnet, so kann die zuständige Behörde die betroffene Person zur Sicherstellung des Vollzugs nach Art. 76 Abs. 1 lit. b Ziff. 3 AuG (SR 142.20) in Haft nehmen, wenn konkrete Anzeichen befürchten lassen, dass sie sich der Ausschaffung entziehen will. Gemäss dieser Bestimmung ist dies insbesondere dann der Fall, wenn die Person ihrer Mitwirkungspflicht nach Art. 90 AuG sowie Artikel 8 Abs. 1 lit. a oder Art. 8 Abs. 4 des Asylgesetzes vom 26. Juni 1998 (AsylG; SR 142.31) nicht nachkommt. Art. 90 AuG besagt, dass die Ausländerinnen und Ausländer insbesondere verpflichtet sind, zutreffende und vollständige Angaben über die für die Regelung des Aufenthalts wesentlichen Tatsachen zu machen (lit. a), die erforderlichen Beweismittel unverzüglich einzureichen oder sich darum bemühen, sie innerhalb einer angemessenen Frist zu beschaffen (lit. b) und Ausweispapiere zu beschaffen oder bei deren Beschaffung durch die Behörden mitzuwirken (lit. c). Gemäss <ref-law> sind Asylsuchende verpflichtet, an der Feststellung des Sachverhaltes mitzuwirken und insbesondere ihre Identität offen zu legen. <ref-law> statuiert darüber hinaus die Verpflichtung, nach Vorliegen eines vollziehbaren Wegweisungsentscheides bei der Beschaffung gültiger Reisepapiere mitzuwirken.
2.3 Das Haftgericht III Bern-Mittelland hat ausgeführt, es sei zur Zeit davon auszugehen, dass der Beschwerdeführer nicht wie von ihm angegeben aus Bangladesch stamme, sondern vielmehr indischer Staatsangehöriger sei. Die Vorinstanz stützt sich dabei auf Erkenntnisse des BFM, welche wiederum auf entsprechenden Informationen der Behörden von Bangladesch, Abklärungen durch Vertrauensanwälte in Bangladesch und Indien sowie auf Aussagen von mehreren Drittpersonen beruhen. Der Beschwerdeführer zeigt nicht substantiiert auf, inwiefern die Sachverhaltsfeststellung der Vorinstanz offensichtlich unrichtig sein soll; vielmehr beschränkt er sich auf ein blosses Bestreiten seiner indischen Staatsangehörigkeit, was für eine Sachverhaltsrüge gemäss <ref-law> und <ref-law> nicht genügt (<ref-ruling> E. 2.2 S. 246; <ref-ruling> E. 1.4.3 S. 255).
Der Beschwerdeführer machte in diesem Zusammenhang eventualiter geltend, das BFM und der Migrationsdienst des Kantons Bern hätten das Beschleunigungsgebot verletzt, indem sie nach Erhalt der Information der Behörden von Bangladesch über seine Staatsangehörigkeit keinerlei Bemühungen unternommen hätten, indische Reisepapiere zu beschaffen. Diese Rüge geht fehl: Der Vernehmlassung des BFM kann entnommen werden, dass dieses die betreffende Auskunft am 29. April 2008 erhielt und am 11. Juni 2008 Vertrauensanwälte sowohl in Bangladesch als auch in Indien eingesetzt hat, um weitere Informationen erhältlich zu machen; es begründet sein Vorgehen damit, dass die indische Vertretung in der Schweiz nur dann in der Lage sei, ein Ersatzreisedokument auszustellen, wenn die Herkunft und Identität der betroffenen Person zweifelsfrei feststünden. Nach Erhalt der ersten Abklärungsergebnisse am 19. August bzw. 11. September 2008 wurden am 19. September 2008 weitere Abklärungen via Vertrauensanwalt in Indien in Auftrag gegeben, deren Ergebnisse dem BFM am 6. November 2008 zugingen. Von einer Verletzung des Beschleunigungsgebots kann bei dieser Sachlage keine Rede sein.
Auch die in der ergänzenden Eingabe des Beschwerdeführers vom 17. November 2008 behauptete Verletzung des rechtlichen Gehörs ist nicht zu erkennen: Der Beschwerdeführer rügt, dass ihm der Bericht des Vertrauensanwaltes aus Indien nie zugestellt worden sei. Es wäre dem Beschwerdeführer jedoch freigestanden, beim BFM bzw. beim Migrationsdienst des Kantons Bern um Einsicht in die ihn interessierenden Akten zu ersuchen. Dass ihm eine solche Einsicht verweigert wurde, wird selbst vom Beschwerdeführer nicht behauptet.
Die einstweilige Annahme des Haftgerichtes III Bern-Mittelland, dass der Beschwerdeführer aus Indien und nicht wie von ihm angegeben aus Bangladesch stamme, lässt sich daher nicht beanstanden.
2.4 Der Beschwerdeführer führt ins Feld, dass durch seine Inhaftierung vor allem Druck auf seine Mutter gemacht und deren Verhalten sanktioniert werden soll. Er übersieht dabei jedoch, dass die Pflicht, wahrheitsgemässe Angaben zu seiner Herkunft zu machen bzw. falsche Angaben zu korrigieren, nicht nur seine Mutter, sondern auch ihn persönlich trifft. Da er die zuständigen Behörden dennoch nicht über seine tatsächliche Nationalität aufklärte, hat die Vorinstanz zu Recht auf Verletzung seiner Mitwirkungspflichten und somit auf Untertauchensgefahr i.S.v. Art. 76 Abs. 1 lit. b Ziff. 3 AuG (i.V.m. Art. 90 AuG sowie <ref-law>) geschlossen.
2.5 Wie alle staatlichen Massnahmen muss auch die Ausschaffungshaft verhältnismässig sein. Es ist jeweils aufgrund der konkreten Umstände zu klären, ob sie geeignet bzw. erforderlich ist und nicht gegen das Übermassverbot, d.h. das sachgerechte und zumutbare Verhältnis von Mittel und Zweck, verstösst (<ref-ruling> E. 2.2 S. 100). Dabei ist dem Verhalten des Betroffenen, den die Papierbeschaffung allenfalls erschwerenden objektiven Umständen sowie dem Umfang der von den Behörden bereits getroffenen Abklärungen Rechnung zu tragen. Ebenso ist zu berücksichtigen, wieweit der Betroffene es tatsächlich in der Hand hat, seine Festhaltung zu beenden, indem er seiner Mitwirkungs- bzw. Ausreisepflicht nachkommt. Im vorliegenden Fall haben die schweizerischen Behörden Abklärungen mittels Vertrauensanwälten in Indien und Bangladesch getätigt, um die Staatsbürgerschaft des Beschwerdeführers zu eruieren. Das BFM führt in seiner Vernehmlassung zudem aus, dass die Einreichung eines Identitätsdokuments, aber auch bereits die Angabe der korrekten heimatlichen Adresse das Verifikationsverfahren in Indien beschleunigen könnte. Bei Indien handle es sich zudem um einen verfolgungssicheren Staat, wo aufgrund seiner hohen Bevölkerungszahl zwar Verzögerungen nicht ausgeschlossen seien, sich aber regelmässig keine Probleme hinsichtlich der Rückkehr ergäben. Der Beschwerdeführer bestreitet noch immer, indischer Staatsangehöriger zu sein, und hat soweit ersichtlich keinerlei Bemühungen gezeigt, zur Beschaffung seiner Reisepapiere beizutragen. Damit ist die Anordnung von Ausschaffungshaft zur Sicherstellung des Wegweisungsvollzuges geeignet und erforderlich; dass der Beschwerdeführer erst am 3. März 2009 die Volljährigkeit erreicht, vermag daran nichts zu ändern.
2.6 Die Beschwerde erweist sich bereits aufgrund des bisher Gesagten als unbegründet. Ob der Beschwerdeführer darüber hinaus mit Betäubungsmitteln gehandelt hat, ob er mittel- und obdachlos ist und ob er zu erkennen gab, dass er nicht zurück in sein Heimatland wolle, ist daher für den vorliegenden Entscheid nicht mehr relevant: Diese Umstände würden zwar die Untertauchensgefahr erhöhen; nach dem Ausgeführten bestehen jedoch auch ohne Berücksichtigung der erwähnten Umstände Haftgründe.
3. Der Beschwerdeführer beantragt, es sei ihm für das Verfahren vor Bundesgericht die unentgeltliche Rechtspflege und Verbeiständung zu gewähren.
Das Bundesgericht befreit eine Partei, die nicht über die erforderlichen Mittel verfügt, auf Antrag von der Bezahlung der Gerichtskosten und von der Sicherstellung der Parteientschädigung, sofern ihr Rechtsbegehren nicht aussichtslos erscheint (<ref-law>). Wenn es zur Wahrung ihrer Rechte notwendig ist, bestellt das Bundesgericht der Partei einen Anwalt. Nach der Rechtsprechung ist ein Gesuchsteller bedürftig, der die Leistung der erforderlichen Prozess- und Parteikosten nur erbringen kann, wenn er die Mittel angreift, die er zur Deckung des Grundbedarfs für sich und seine Familie benötigt. Als aussichtslos gelten jene Prozessbegehren, deren Gewinnaussichten beträchtlich geringer sind als die Verlustgefahren und die deshalb kaum als ernsthaft bezeichnet werden können. Massgeblich ist, ob sich eine vernünftige, nicht mittellose Partei ebenfalls zur Beschwerde entschlossen hätte. Eine Partei soll einen Prozess, den sie auf eigene Rechnung und Gefahr nicht führen würde, nicht deshalb anstrengen können, weil er sie nichts kostet (<ref-ruling> E. 2.3.1; <ref-ruling> E. 2.5.3). Das Gesetz bezieht sich auf die Aussichtslosigkeit der Rechtsbegehren und nicht einzelner Rügen, weswegen die Chancen der Beschwerde als Ganzes massgebend sind (Urteil 6B_588/2007 vom 11. April 2008 E. 6.2).
Von der Mittellosigkeit des Beschwerdeführers ist aufgrund der Akten ohne weiteres auszugehen. Die Beschwerde ist in ihrer Gesamtheit nicht geradezu als offensichtlich unbegründet und aussichtslos zu bezeichnen. Die Minderjährigkeit des Beschwerdeführer rechtfertigt unter den vorliegenden Umständen eine anwaltliche Vertretung. Dem Gesuch des Beschwerdeführers um unentgeltliche Rechtspflege und Verbeiständung kann demnach entsprochen werden.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten wird abgewiesen.
2. Das Gesuch des Beschwerdeführers um unentgeltliche Rechtspflege und Verbeiständung für das Verfahren vor Bundesgericht wird gutgeheissen:
2.1 Es werden keine Kosten erhoben.
2.2 Dem Beschwerdeführer wird Fürsprecher Thomas Wenger, Bern, als unentgeltlicher Rechtsbeistand beigegeben; dieser wird für das bundesgerichtliche Verfahren mit insgesamt Fr. 1'000.-- aus der Bundesgerichtskasse entschädigt.
3. Dieses Urteil wird den Parteien, dem Haftgericht III Bern-Mittelland (Haftrichterin 7) und dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 25. November 2008
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Merkli Zähndler