Sachverhalt: A. A.a. X._ (Darlehensnehmer, Beschwerdeführer) begann im Jahr 2001 mit dem Studium der Rechtswissenschaft. Zur Finanzierung seines Studiums schloss er im September bzw. Oktober 2003 mit der Bank Y._ (Darlehensgeberin, Beschwerdegegnerin) einen Basisvertrag und einen "Bildung plus-Kreditvertrag" über eine Summe von Fr. 20'000.-- ab. Dieser Betrag wurde in Form eines Überziehungskredits auf laufendem Konto gewährt, wobei die Überziehungslimite gestaffelt erhöht werden sollte. Der Kredit sollte gemäss Vereinbarung ausschliesslich der Finanzierung der mehrjährigen Hochschulausbildung dienen. Der Zins von 3,25 bzw. 3 % wurde gemäss Vertrag bis zum Ende der Ausbildung kapitalisiert. A.b. Jeweils auf Antrag des Darlehensnehmers wurde der Kredit im November 2004 zuerst auf Fr. 35'000.-- und im Januar 2007 auf Fr. 37'000.-- erhöht. Die Darlehensgeberin nahm unbestrittenermassen nie eine Kreditfähigkeitsprüfung nach den Regeln von Art. 28 des Bundesgesetzes vom 23. März 2001 über den Konsumkredit (KKG; SR 221.214.1) vor, verlangte aber vor der ersten Anhebung der Kreditlimite im Jahr 2004 ein detailliertes Budget. A.c. Der Darlehensnehmer hielt die gewährten Kreditlimiten nicht immer ein und wurde zwischen Oktober 2006 und Oktober 2008 mehrfach zum Ausgleich des Überzugssaldos aufgefordert. Nachdem das im dritten Kreditvertrag vorgesehene voraussichtliche Ausbildungsende verstrichen war, teilte der Darlehensnehmer der Darlehensgeberin mit, es sei ihm nicht möglich, den Überzug auszugleichen. Er sei übermässig überschuldet und studiere noch. Zur Begründung verwies der Darlehensnehmer auf Bandscheibenprobleme, welche zu einer temporären Exmatrikulation und einer kostspieligen Operation geführt hätten. A.d. Der Darlehensnehmer schlug in der Folge vor, den Kredit nach Abschluss des Studiums monatlich abzuzahlen. Die Darlehensgeberin unterbreitete ihm daraufhin eine Abzahlungsvereinbarung, die eine Schuldanerkennung und konkrete Rückzahlungsmodalitäten beinhaltete. Zudem erklärte sie unter der Bedingung der Einhaltung der Abzahlungsvereinbarung den Verzicht auf die laufenden Zinsen ab Ende 2008. Der Darlehensnehmer lehnte die Unterzeichnung der Vereinbarung ab. Daraufhin kündigte die Darlehensgeberin mit Schreiben vom 7. August 2009 den "Bildung plus-Kreditvertrag" und verlangte die Rückzahlung des ihrer Ansicht nach offenen Betrags von Fr. 37'939.78 bis zum 31. August 2009. Da die Rückzahlung ausblieb, leitete die Darlehensgeberin die Betreibung ein. Gegen den Zahlungsbefehl vom 18. September 2009 erhob der Darlehensnehmer Rechtsvorschlag. B. B.a. Am 5. Oktober 2010 reichte die Darlehensgeberin beim Gerichtskreis VIII Bern-Laupen (neu: Regionalgericht Bern-Mittelland) Klage ein und beantragte, der Darlehensnehmer sei zur Zahlung eines Betrags von Fr. 37'939.80 zu verurteilen und der Rechtsvorschlag in der gegen ihn eingeleiteten Betreibung sei zu beseitigen. Der Darlehensnehmer beantragte widerklageweise, die Darlehensgeberin sei zur Rückzahlung der durch ihn bereits geleisteten Zinszahlungen zu verurteilen. Mit Entscheid vom 26. Oktober 2011 hiess der Gerichtspräsident des Regionalgerichts Bern-Mittelland die Klage teilweise gut, verurteilte den Darlehensnehmer zur Zahlung von Fr. 37'000.-- und beseitigte den Rechtsvorschlag in diesem Umfang. Die Widerklage wurde abgewiesen. B.b. Dagegen erhob der Darlehensnehmer Berufung beim Obergericht das Kantons Bern und beantragte, es sei der erstinstanzliche Entscheid aufzuheben, die Klage abzuweisen und die Darlehensgeberin zur Zahlung von Fr. 4'686.85 zu verurteilen. Mit Entscheid vom 3. September 2012 wies das Obergericht des Kantons Bern die Berufung ab. C. Mit Beschwerde in Zivilsachen vom 28. September 2012 beantragt der Darlehensnehmer dem Bundesgericht, es sei der Entscheid des Obergerichts aufzuheben, die Klage abzuweisen und die Beschwerdegegnerin zur Zahlung von Fr. 4'686.85 zu verurteilen. Eventuell sei die Sache zu neuer Beurteilung an die Vorinstanz zurückzuweisen. Die Beschwerdegegnerin beantragt die Abweisung der Beschwerde. Die Vorinstanz hat auf eine Vernehmlassung verzichtet. 