Sachverhalt:
A. In der Betreibung Nr. xxxx des Betreibungsamts Oberland (Dienststelle Ost) gegen X._ erteilte das Regionalgericht Bern Oberland der Betreibungsgläubigerin mit Entscheid vom 2. Mai 2011 provisorische Rechtsöffnung für Forderungen aus einem Mietvertrag. Diesen Entscheid focht X._ ohne Erfolg beim Obergericht des Kantons Bern sowie beim Bundesgericht an (vgl. Urteil 5A_748/2011 vom 26. Oktober 2011).
Anlässlich der Pfändung vom 29. Juni 2011 gab X._ u.a. einen Mietzins inkl. Nebenkosten in der Höhe von Fr. 960.-- zu Protokoll. Am 16. August 2011 stellte das Betreibungsamt Oberland, Dienststelle Oberland Ost, die Pfändungsurkunde aus, die gleichzeitig als Verlustschein nach Art. 115 Abs. 1 und Art. 149 SchKG dient (Gesamtbetrag Fr. 39'836.95). Das Betreibungsamt hielt fest, beim Schuldner könne weder Vermögen noch künftiger Lohn gepfändet werden und verwies auf die Existenzminimumsberechnung, welche keine pfändbare Quote aufwies.
Mit einer als Beschwerde betitelten Eingabe wandte sich X._ am 18. August 2011 an die "Aufsichtsbehörde des Betreibungsamtes Oberland, Dienststelle Oberland Ost [...]". Darin beantragte X._ - unter Hinweis auf das damals noch hängige Rechtsmittelverfahren in Sachen Rechtsöffnung - die Aufhebung des Verlustscheines.
Mit Verfügung vom 24. August 2011 hob das Betreibungsamt den Verlustschein auf und ersuchte die Gläubigerin sowie X._ um Rücksendung des Verlustscheines bzw. dessen Doppels. Gleichzeitig wurde X._ um Mitteilung ersucht, ob die Beschwerde infolgedessen als zurückgezogen betrachtet werden könne.
B. Gegen diese Verfügung erhob X._ mit Eingabe vom 30. August 2011 erneut Beschwerde und beantragte sinngemäss ihre Aufhebung wegen Verletzung von kantonalem und interkantonalem Verfahrensrecht. Am 6. September 2011 retournierte die Gläubigerin den Originalverlustschein an das Betreibungsamt. Das Obergericht des Kantons Bern wies die Beschwerde vom 30. August (zusammen mit der Beschwerde vom 18. August 2011) mit Entscheid vom 23. November 2011 ab, soweit es darauf eintrat bzw. soweit die Beschwerden nicht als gegenstandslos abzuschreiben waren.
C. Mit Beschwerde vom 5. Dezember 2011 gelangt X._ (nachfolgend: Beschwerdeführer) an das Bundesgericht und verlangt die Aufhebung des vorinstanzlichen Entscheids wegen Verletzung von Bundesrecht, von Völkerrecht, von kantonalen verfassungsmässigen Rechten und "wegen des schweren Mangels der offensichtlich unrichtigen Feststellung des rechtserheblichen Sachverhalts" (Ziffer 1); des weiteren sei das Betreibungsamt Oberland zu verpflichten, gegen ihn weder einen provisorischen noch einen definitiven Verlustschein über den Totalbetrag von Fr. 39'836.95 auszustellen (Ziffer 2); ausserdem sei das Betreibungsamt Oberland zu verpflichten, seine Verfügungen vom 16. August 2011 bzw. 4. Juli 2011 betreffend Existenz-Minimum dahingehend zu berichtigen, dass die besonders schützenswerten Personendaten "Die Schuldnerin wird vollumfänglich durch den Sozialdienst Frutigen unterstützt" und "Lohnart: Fürsorgeleistungen" gestrichen werden und dass der Betriebene zur Bestimmung des betreibungsrechtlichen Existenz-Minimums und Notbedarfs kein fixes Nettoeinkommen pro Monat von Fr. 1'796.05 erzielt und dass er einen mietvertragsgemäss geschuldeten und bezahlten Mietzins inkl. Nebenkosten von Fr. 800.-- ausgewiesen hat (Ziffer. 3).
Schliesslich verlangt der Beschwerdeführer die aufschiebende Wirkung sowie die unentgeltliche Rechtspflege und Rechtsvertretung (Ziffern 4 und 5).
Mit Verfügung vom 6. Dezember 2011 wies die Präsidentin der II. zivilrechtlichen Abteilung das Gesuch um aufschiebende Wirkung ab.
Es wurden die Akten, jedoch keine Vernehmlassungen eingeholt.

Erwägungen:
1. Angefochten ist ein Entscheid einer kantonalen Aufsichtsbehörde in Schuldbetreibungs- und Konkurssachen, welcher gemäss <ref-law> der Beschwerde in Zivilsachen unterliegt, ohne dass es auf den Streitwert ankommt (<ref-law>). Der vorliegende Entscheid der kantonalen Aufsichtsbehörde ist ein Endentscheid im Sinne von <ref-law> (<ref-ruling> E. 1.2 S. 351). Die fristgemäss erhobene Beschwerde in Zivilsachen ist grundsätzlich zulässig.
2. Mit Rechtsbegehren Ziffer 2 beantragt der Beschwerdeführer im Wesentlichen, dem Betreibungsamt Oberland sei zu untersagen, gegen ihn in der laufenden Betreibung "während der Dauer der wirksamen Ausübung des Beschwerderechts über die Streitigkeiten in Bezug auf zivilrechtliche Ansprüche und Verpflichtungen" einen provisorischen oder definitiven Verlustschein über den Totalbetrag von Fr. 39'836.95 auszustellen.
Die Vorinstanz hielt fest, dass das Beschwerdeverfahren mit der Verfügung des Betreibungsamts Oberland, die den Verlustschein aufhob, insoweit gegenstandslos wurde. Der Beschwerdeführer legt nicht dar, warum dies nicht der Fall sein sollte bzw. worin sein Rechtsschutzinteresse besteht.
Soweit der Beschwerdeführer mit seinem Rechtsbegehren Ziffer 2 verlangt, es sei dem Betreibungsamt Oberland generell zu untersagen in der laufenden Betreibung ihm gegenüber einen provisorischen oder definitiven Verlustschein auszustellen, fehlt es an einem Anfechtungsobjekt.
3. Mit seinem Rechtsbegehren Ziffer 3 verlangt der Beschwerdeführer eine Berichtigung der Verfügung vom 16. August 2011 (Pfändungsurkunde als Verlustschein; vgl. <ref-law>) bzw. der Verfügung vom 4. Juli 2011 (Berechnung des Existenzminimums gemäss Rückseite des vorerwähnten Verlustscheins).
Da die beanstandete Berechnung des Existenzminimus Bestandteil des Verlustscheins vom 16. August 2011 bildet und dieser Verlustschein aufgehoben wurde, hat der Beschwerdeführer kein Rechtschutzinteresse an einer Berichtigung von Verlustschein bzw. Existenzminimumsberechnung (<ref-law>). Überdies legt er auch nicht dar, warum ihm ein solches Rechtsschutzinteresse zukommen sollte. Darauf ist nicht einzutreten.
4. Soweit der Beschwerdeführer den vorinstanzlichen Entscheid aus sonstigen materiellrechtlichen Gründen (namentlich solche mietrechtlicher oder arrestrechtlicher Art) kritisiert bzw. aufgehoben haben will, sind diese einer Überprüfung im Beschwerdeverfahren nicht zugänglich und kommt der Beschwerdeführer der ihm gemäss <ref-law> obliegenden Begründungspflicht - mangels nachvollziehbarer Überlegungen insbesondere zur Bundesverfassung sowie zur EMRK - nicht nach. Zudem legt er nicht dar, weshalb die Aufsichtsbehörde zu seinen datenschutzrechtlichen Überlegungen hätte Stellung nehmen müssen. Darauf ist nicht einzutreten.
5. Bei diesem Ausgang des Verfahrens hat der Beschwerdeführer für die Gerichtskosten aufzukommen (<ref-law>). Wie den vorstehenden Ausführungen entnommen werden kann, konnte der Beschwerde von Beginn weg kein Erfolg beschieden sein, weshalb es an einer materiellen Voraussetzung für die Gewährung der unentgeltlichen Rechtspflege mangelt (<ref-law>) und das Gesuch entsprechend abzuweisen ist.

Demnach erkennt das Bundesgericht:
1. Auf die Beschwerde wird nicht eingetreten.
2. Das Gesuch um unentgeltliche Rechtspflege des Beschwerdeführers wird abgewiesen.
3. Die Gerichtskosten von Fr. 1'500.-- werden dem Beschwerdeführer auferlegt.
4. Dieses Urteil wird den Parteien, dem Betreibungsamt Oberland, Dienststelle Oberland Ost, und dem Obergericht des Kantons Bern, Aufsichtsbehörde in Betreibungs- und Konkurssachen, schriftlich mitgeteilt.
Lausanne, 6. Januar 2012
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Hohl
Der Gerichtsschreiber: Schwander