Sachverhalt:
A. X._ (geb. 1968) und Y._ (geb. 1970) heirateten am 4. August 1995 in A._. Aus ihrer Ehe gingen die Kinder B._ (geb. 1996) und C._ (geb. 1999) hervor. Im Jahr 2006 trennten sich die Parteien. X._ wurde im damaligen Eheschutzverfahren verpflichtet, monatliche Unterhaltsbeiträge von Fr. 750.-- pro Kind und von Fr. 1'400.-- für Y._ zu bezahlen.
B. Am 23. September 2010 leitete X._ beim Richteramt D._ das Scheidungsverfahren ein. Ein in diesem Verfahren eingereichtes Gesuch um Abänderung der Unterhaltsbeiträge wies der zuständige Richter ab.
Durch Scheidungsurteil vom 1. Februar 2012 stellte der Amtsgerichtspräsident des Richteramts D._ die beiden Kinder unter die elterliche Sorge der Mutter, die Kinderunterhaltsbeiträge setzte er auf Fr. 750.-- fest. Er nahm Kenntnis, dass die im hälftigen Miteigentum befindliche vormals eheliche Liegenschaft der Parteien von X._ zu Alleineigentum übernommen werde. Die hierfür von X._ geschuldete güterrechtliche Ausgleichszahlung setzte er auf Fr. 124'384.70 zuzüglich Zins fest, wobei ein Betrag von Fr. 20'000.-- bis Ende April 2012, der Restbetrag in monatlich Raten von Fr. 800.-- ab Mai 2012 auszurichten sei. Weiter hielt der Richter dafür, dass X._ aufgrund der Ratenzahlungen aus Güterrecht keinen nachehelichen Unterhalt an die Ehefrau bezahlen könne. Auf der Seite der Ehefrau stellte er eine Unterdeckung von Fr. 1'300.-- pro Monat fest.
C. Gegen dieses Urteil erhoben beide Parteien Berufung an das Obergericht des Kantons Solothurn. Y._ beantragte die Zusprechung eines bis November 2015 befristeten Unterhaltsbeitrages an sie selbst von Fr. 850.-- unter Aufschiebung der Ratenzahlungen aus Güterrecht bis nach dem Wegfall der Unterhaltspflicht. X._ verlangte eine Reduktion der Ausgleichszahlung auf Fr. 35'384.70, eventualiter auf Fr. 69'884.70.
Mit Urteil vom 4. Dezember 2012 hiess das Obergericht die Berufung von Y._ in der Hauptsache gut. Die Berufung von X._ wies es ab, soweit darauf eingetreten wurde. Die umstrittenen Ziffern des Scheidungsurteils vom 1. Februar 2012 formulierte das Obergericht neu wie folgt:
6. X._ hat der Ehefrau einen monatlich vorauszahlbaren Unterhaltsbeitrag von Fr. 835.-- zu bezahlen. Die Unterhaltsbeitragspflicht dauert bis 30. November 2015.
7. Es wird festgestellt, dass die Ehefrau eine Unterdeckung von Fr. 491.-- aufweist.
9. b) Der Ehemann hat der Ehefrau eine güterrechtliche Ausgleichszahlung von Fr. 124'384.70, zuzüglich Zins zu 5% ab Fälligkeit (Rechtskraft des Urteils), zu leisten, wobei er den Betrag von Fr. 20'000.-- bis Ende Januar 2013 zu bezahlen hat. Den verbleibenden Restbetrag der Schuld hat der Ehemann in aufeinanderfolgenden monatlichen Raten von Fr. 800.--, erstmals auf den 1. Dezember 2015 auszurichten.
Ab Wegfall der Unterhaltsverpflichtung gegenüber den Kindern bei Erreichen von deren wirtschaftlichen Selbständigkeit erhöhen sich die Ratenzahlungen um den Betrag der weggefallenen Unterhaltszahlungen.
Die Ehefrau hat das Recht, ihre Güterrechtsforderung gegenüber dem Ehemann zufolge des Zahlungsaufschubs zulasten des GB A._ Nr. xxxx zu ihren Gunsten grundpfandrechtlich sicherzustellen und eine Grundpfandverschreibung zu errichten.
D. Mit Postaufgabe vom 28. Januar 2013 hat X._ (Beschwerdeführer) Beschwerde an das Bundesgericht erhoben. Er beantragt, die Unterhaltsverpflichtung gegenüber Y._ (Beschwerdegegnerin) sei aufzuheben und diesbezüglich das erstinstanzliche Urteil zu bestätigen. Ziffer 9 lit. b Absatz 1 des Scheidungsurteils sei dahin gehend zu ändern, dass er der Beschwerdegegnerin eine güterrechtliche Ausgleichszahlung von Fr. 45'384.70, eventualiter von Fr. 79'384.70 leiste, wobei er den Betrag von Fr. 20'000.-- bis Ende Januar 2013 bezahle und den verbleibenden Restbetrag ab Rechtskraft des Urteils in monatlichen Raten von Fr. 800.--; bisherige Zahlungen seien anzurechnen. Weiter sei seiner Beschwerde für die Zahlung der Fr. 20'000.-- die aufschiebende Wirkung zu erteilen. Für das bundesgerichtliche Verfahren ersucht er um unentgeltliche Rechtspflege und um Einsetzung seines Anwalts als unentgeltlichen Rechtsbeistand.
Die Beschwerdegegnerin hat mit Vernehmlassung vom 30. Januar 2013 auf Abweisung des Gesuchs um aufschiebende Wirkung geschlossen. Sie beantragt ihrerseits die unentgeltliche Rechtspflege für das bundesgerichtliche Verfahren. Die Vorinstanz verzichtete auf eine Stellungnahme zur aufschiebenden Wirkung.
E. Mit Verfügung vom 5. Februar 2013 hat der Präsident der II. zivilrechtlichen Abteilung des Bundesgerichts der Beschwerde für die Anzahlung von Fr. 20'000.-- die aufschiebende Wirkung gewährt.
In der Sache selbst hat das Bundesgericht keine Vernehmlassungen eingeholt.

Erwägungen:
1. 1.1 Angefochten sind die Fr. 30'000.-- übersteigenden vermögensrechtlichen Folgen eines kantonal letztinstanzlichen Ehescheidungsurteils (Art. 72 Abs. 1, Art. 74 Abs. 1 lit. b, Art. 75 Abs. 1, Art. 90 BGG). Der Beschwerdeführer ist gemäss <ref-law> zur Beschwerde berechtigt. Die Beschwerdefrist (<ref-law>) ist ebenfalls eingehalten, womit die Beschwerde in Zivilsachen grundsätzlich zulässig ist.
1.2 Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>). Allerdings ist in der Beschwerdeschrift in gedrängter Form darzulegen, inwiefern der angefochtene Akt Recht verletzt (<ref-law>; <ref-ruling> E. 1.4.1 S. 254).
Dabei ist das Bundesgericht grundsätzlich an den von der Vorinstanz festgestellten Sachverhalt gebunden (<ref-law>). Diesbezüglich kann einzig vorgebracht werden, er sei offensichtlich unrichtig festgestellt worden (<ref-law>) oder er beruhe auf einer anderen Rechtsverletzung im Sinne von <ref-law> (z.B. <ref-law> oder <ref-law>). Ausserdem muss in der Beschwerde aufgezeigt werden, inwiefern die Behebung der vorerwähnten Mängel für den Ausgang des Verfahrens entscheidend sein kann (<ref-law> in fine). Für all diese Elemente gilt das strenge Rügeprinzip (<ref-law>; <ref-ruling> E. 1.4.2 S. 254). Das bedeutet, dass das Bundesgericht nur klar und detailliert erhobene und soweit möglich belegte Rügen prüft, während es auf ungenügend begründete Rügen und rein appellatorische Kritik am angefochtenen Entscheid nicht eintritt (<ref-ruling> E. 2.2 S. 246).
2. Die Vorinstanz ging - grösstenteils unter Verweis auf das Urteil des Amtsgerichtspräsidenten vom 1. Februar 2012 - vom nachfolgend dargestellten Sachverhalt aus.
2.1 Die Beschwerdegegnerin weist einen monatlichen Bedarf inklusive Kindern von Fr. 5'310.-- auf. Angesichts des ihr angerechneten (hypothetischen) Einkommens von Fr. 2'484.-- und Kinderunterhaltsbeiträgen von insgesamt Fr. 1'500.-- ergibt sich ein Manko von rund Fr. 1'300.--. Beim Beschwerdeführer resultiert nach Deckung seines eigenen Bedarfs ein Einkommensüberschuss von Fr. 835.--.
Auf der Basis dieser vorliegend nicht mehr bestrittenen Bedarfs- und Einkommenszahlen setzte die Vorinstanz den vom Beschwerdeführer der Beschwerdegegnerin auszurichtenden nachehelichen Unterhaltsbeitrag auf Fr. 835.-- fest, geschuldet bis und mit 30. November 2015 (bis zum 16. Geburtstag des jüngeren Sohnes).
2.2 Die Parteien sind je hälftig Miteigentümer der vormals ehelichen Liegenschaft GB A._ Nr. xxxx, welche sie durch eigene Mittel (je Fr. 40'000.--) und durch Aufnahme einer Hypothek, die sich per 31. Dezember 2011 auf Fr. 290'000.-- belief, finanziert hatten. Die Liegenschaft wird weiterhin vom Beschwerdeführer bewohnt. Das Nachbargrundstück gehört dem Vater des Beschwerdeführers. Bereits vor den Vorinstanzen waren sich die Parteien einig, dass der Beschwerdeführer die Liegenschaft zu Alleineigentum übernehmen wird und die Übertragung gegen Übernahme der Schuld und Leistung einer Ausgleichszahlung an die Ehefrau geschehen solle. Umstritten war und ist jedoch die Höhe dieses Betrages, worauf zurückzukommen sein wird.
Auf der Grundlage einer gemeinsam von den Parteien in Auftrag gegebenen Verkehrswertschätzung von E._, dipl. Architekt FH, welcher den Verkehrswert der Liegenschaft auf Fr. 523'000.-- bezifferte, setzte der erstinstanzliche Richter die Ersatzforderung des Eigenguts der Ehefrau auf Fr. 116'500.-- fest (Fr. 523'000.-- - Fr. 290'000.-- = Fr. 233'000.--, geteilt durch zwei). Die Ausgleichszahlung aus der Errungenschaft der Parteien setzte er auf Fr. 7'884.70 fest, was den Totalbetrag von Fr. 124'384.70 ergab. Die Vorinstanz schützte diese Berechnung.
2.3 Anders als der erstinstanzliche Richter gab die Vorinstanz unter Berufung auf <ref-ruling> dem nachehelichen Unterhalt den Vorrang gegenüber der Abzahlung des güterrechtlichen Ausgleichsbetrages. Sie regelte die Zahlungsmodalitäten dergestalt, dass Fr. 20'000.-- bis Ende Januar 2013 und der verbleibende Restbetrag in monatlichen Raten von Fr. 800.-- zu leisten seien, wobei für diese Raten in Anwendung von <ref-law> Zahlungsfristen bis zum Wegfall der Unterhaltsbeiträge an die Beschwerdegegnerin gewährt wurden (Abzahlungsbeginn 1. Dezember 2015; vgl. vorstehend C.).
3. In diesem Zusammenhang rügt der Beschwerdeführer eine Verletzung von Art. 125 Abs. 2 Ziff. 5 und <ref-law>.
3.1 Der Beschwerdeführer bringt vor, die Vorinstanz habe den nachehelichen Unterhaltsbeitrag zugesprochen, ohne zuvor über die güterrechtliche Ausgleichszahlung befunden zu haben. Der Unterhalt sei aber erst nach Durchführung der güterrechtlichen Auseinandersetzung festzusetzen.
3.2 Es trifft zu, dass über Unterhaltsbeiträge unter Berücksichtigung des Ergebnisses der güterrechtlichen Auseinandersetzung zu befinden ist (<ref-law>; <ref-ruling> E. 4 S. 544 f.). Dadurch soll sichergestellt werden, dass das Ergebnis der güterrechtlichen Auseinandersetzung im Rahmen der Eigenversorgungskapazität beider Parteien berücksichtigt wird. Entgegen den Behauptungen des Beschwerdeführers ist die Vorinstanz auch so vorgegangen. So stand fest, dass der Beschwerdeführer angesichts seiner Eigenversorgungskapazität einen Betrag von Fr. 835.-- bezahlen kann, während die Beschwerdegegnerin den Bedarf von sich und den Kindern nicht decken kann.
Der Beschwerdeführer verlangt demgegenüber etwas anderes, nämlich dass die Abzahlungsraten in seinem persönlichen Bedarf zu berücksichtigen seien, was gemäss <ref-ruling> aber unzulässig ist. Er verwechselt insofern die Frage der Festsetzung von Unterhaltsbeitrag und Ausgleichszahlung mit der Frage der Regelung der Modalitäten für die Begleichung des festgesetzten Ausgleichsbetrages. Wie aus <ref-ruling> ersichtlich ist, geht der nacheheliche Unterhalt der privaten Schuldentilgung, wozu auch die Abzahlung güterrechtlicher Ausgleichsbeträge gehört, vor. Nichts anderes hat die Vorinstanz festgehalten; sie führte aus, dass die Unterhaltsverpflichtung der "Tilgung" der güterrechtlichen Herausschuldigkeit vorgehe (angefochtenes Urteil E. 3 S. 7).
Die Gewährung der Ratenzahlung inkl. Zahlungsaufschub gemäss <ref-law> war ein Entgegenkommen gegenüber dem Beschwerdeführer, was den Beschwerdeführer bereits insofern besser stellt, als ihm daraus Zins- und konjunkturelle Vorteile entstehen. Die erstinstanzliche Lösung, wie sie dem Beschwerdeführer vorschwebt, würde zu einer weiteren Schlechterstellung der Beschwerdegegnerin führen. Die Tilgungsrate im Grundbedarf des Beschwerdeführers zu berücksichtigen, würde bedeuten, die Beschwerdegegnerin indirekt an der Bezahlung ihres güterrechtlichen Guthabens zu beteiligen (vgl. <ref-ruling> E. 3.b S. 293; zuletzt bestätigt in 5A_390/2012 vom 21. Januar 2013 E. 6.3).
Die von der Vorinstanz getroffene Regelung ist somit nicht zu beanstanden.
4. Sodann rügt der Beschwerdeführer, die Vorinstanz habe den güterrechtlichen Ausgleichsbetrag in zweifacher Hinsicht in Verletzung von Bundesrecht (<ref-law> und <ref-law>) festgesetzt und sie habe den Sachverhalt offensichtlich unrichtig festgestellt, indem von ihm geltend gemachte Eigenleistungen in der Höhe von Fr. 20'000.-- nicht berücksichtigt worden seien.
4.1 Bereits die erste Instanz hielt fest, dass beide Parteien Eigenleistungen im Umfang von je Fr. 20'000.-- geltend gemacht hätten, aber keine Partei belegen könne, wie viel Arbeits- und Materialaufwand tatsächlich in die eheliche Liegenschaft gesteckt worden sei; beide Forderungen seien somit unsubstanziiert und durch nichts belegt und es bestünden keine verlässlichen Hinweise auf die Höhe der Eigenleistungen. Die Vorinstanz knüpfte daran an und verwies auf Aussagen der Parteien vom 1. Februar 2012 vor dem erstinstanzlichen Richter. Der Ehemann habe damals ausgeführt: "Die Liegenschaft wurde 1997 mit Fr. 80'000.-- (zu je Fr. 40'000.--) Eigenkapital erworben. Ich machte die Sanitärsachen. Wir wollten den Umbau schnell erledigen. Wir holten das Material in der Werkstatt. Verrechnet wurde nichts. Es waren Gratisarbeiten. Es handelt sich etwa um 150 bis 160 Stunden. Ich hatte damals einen Lohn von Fr. 30.-- in der Stunde. Wir haben auch noch [am] Feierabend gearbeitet. Der Vater meiner Ehefrau machte die elektrischen Arbeiten. Wir bezahlten das Material. Die Arbeit war gratis. Es waren deutlich weniger Arbeitsstunden, die ihr Vater aufwendete." Die Ehefrau habe demgegenüber ausgesagt: "Mein Vater hat Eigenleistungen an der Liegenschaft erbracht. Wir haben jeden Abend bis in die Nacht hinein gearbeitet. Er arbeitete gratis für uns. Wir bezahlten nur das Material. Die erbrachten Arbeiten meines Vaters sind etwa im selben Rahmen wie jene meines Ehemannes.
In Würdigung dieser Aussagen kam die Vorinstanz in Übereinstimmung mit dem erstinstanzlichen Richter zum Schluss, dass keine Partei die Höhe der behaupteten Leistungen habe belegen können.
4.2 Im Falle von Eigenleistungen bei einem Hausbau ist neben der Tatsache der erbrachten Leistungen auch deren tatsächlicher Umfang Beweisthema (Urteil 5A_822/2008 vom 2. März 2009 E. 3.3, E. 6.1 mit weiteren Hinweisen).
Der Beschwerdeführer hat gegen die vorinstanzliche Tatsachenfeststellung, dass die Parteien keine Belege zur Höhe der behaupteten Eigenleistungen vorgelegt hätten, keine Sachverhaltsrüge erhoben, womit von diesem Sachverhalt auszugehen ist (vorstehend E. 1.2). Er bringt nur vor, die Ehefrau habe seine Eigenleistungen nicht bestritten. Selbst wenn der Argumentation des Beschwerdeführers gefolgt würde, die Ehefrau habe die von ihm behaupteten Eigenarbeiten anerkannt, könnte dies nur als Beweis dafür dienen, dass Arbeiten erbracht wurden, nicht jedoch als Beweis für den genauen Umfang der Arbeitsleistungen. Denn gerade über die Höhe der Leistungen sind sich die Parteien nicht einig. Es liegt also keine Anerkennung eines Betrages vor.
Zusammengefasst vermag der Beschwerdeführer keine Willkür in Bezug auf die vorinstanzliche Sachverhaltsfeststellung oder Beweiswürdigung aufzuzeigen.
4.3 Die vom Beschwerdeführer zusätzlich ins Feld geführte Rüge betreffend <ref-law> wird insofern gegenstandslos, als <ref-law> die Konsequenzen der Beweislosigkeit regelt. Wenn die Vorinstanz indes - wie vorliegend - aufgrund eines Beweisverfahrens willkürfrei zum Ergebnis gelangt, eine bestimmte Behauptung sei bewiesen oder widerlegt, werden die Regeln zur Beweislastverteilung gegenstandslos (<ref-ruling> E. 3.4 S. 634; <ref-ruling> E. 2.1 S. 649; <ref-ruling> E. 5.4 S. 602).
5. Schliesslich rügt der Beschwerdeführer, dass die Vorinstanzen zu Unrecht ein von ihm in Auftrag gegebenes Zweitgutachten zum Verkehrswert der ehelichen Liegenschaft nicht berücksichtigt hätten (Rügen: Verletzung der Vorschriften über die güterrechtliche Auseinandersetzung gemäss Art. 204 ff., insb. <ref-law>; willkürliche Beweiswürdigung; offensichtlich unrichtige Sachverhaltsfeststellung).
5.1 Die Parteien hatten gemeinsam eine Verkehrswertschätzung bei E._, dipl. Architekt FH, in Auftrag gegeben, in dessen Gutachten vom 6. Januar 2009 der Verkehrswert auf Fr. 523'000.-- geschätzt wurde. Kurze Zeit später holte der Beschwerdeführer einseitig eine von ihm selbst als "Zweitgutachten" bezeichnete Schätzung bei F._, Architekt swb, ein, die am 28. September 2010, d.h. kurz nach Einleitung des Scheidungsverfahrens, erstattet wurde und den Liegenschaftswert auf Fr. 385'000.-- beziffert.
Die Vorinstanzen stützten allein auf das Gutachten E._ ab.
5.2 Der Verkehrswert der Liegenschaft stellt eine Sachverhaltsfrage dar, die in Würdigung der zur Verfügung stehenden Beweise zu klären ist. Der Beschwerdeführer hätte somit darzutun, dass die Vorinstanz in Willkür verfallen ist, indem sie beweiswürdigend allein auf das Gutachten E._ abgestellt und die Schätzung F._ unberücksichtigt gelassen hat (vgl. <ref-law>; <ref-ruling> E. 4.3.1 S. 198 f. mit weiteren Hinweisen). Eine willkürliche Beweiswürdigung liegt insbesondere vor, wenn das Gericht offensichtlich Sinn und Tragweite eines Beweismittels verkannt oder ohne zureichenden Grund ein Beweismittel, das einen anderen Entscheid herbeiführen könnte, nicht zur Kenntnis genommen hat oder aufgrund der festgestellten Grundlagen zu unhaltbaren Schlüssen gekommen ist (vgl. <ref-ruling> E. 2.1 S. 9).
5.3 Wie nachfolgend dargelegt wird, gelingt es dem Beschwerdeführer nicht aufzuzeigen, inwiefern es willkürlich sein soll, dass die Vorinstanz nicht auf das einseitig von ihm in Auftrag gegebene Gutachten F._ abgestellt hat. Seine Einwendungen gegen das Gutachten E._ lassen sich in drei Punkte zusammenfassen (nachfolgend E. 5.3.1 bis E. 5.3.3).
5.3.1 Der Beschwerdeführer beanstandet, dass im Gutachten E._ der zur Liegenschaft gehörende Pool mit Fr. 30'000.-- zum Realwert geschlagen wurde (im Gutachten F._ wurde der Betrag abgezogen). Der Beschwerdeführer wiederholt dabei das bereits vor der Vorinstanz vorgebrachte Argument, dass der Pool in das Grundstück seines Vaters rage, was jede Privatsphäre ausschliesse. Das Überbaurecht habe nur begründet werden können, weil der Dienstbarkeitsbelastete sein Vater sei; dieser müsse aber nicht dulden, dass dereinst Fremde in seinem Garten schwimmen, weshalb im Falle eines Verkaufs der Liegenschaft das Überbaurecht im Sinne einer Realobligation einvernehmlich aufgehoben werden müsste.
Wie die Vorinstanz festgestellt hat, ist das Überbaurecht im Grundbuch eingetragen, woran ein Verkauf der Liegenschaft nichts ändern wird. Durch den Pool ist offensichtlich ein Mehrwert gegeben, dessen Höhe vom Beschwerdeführer im Übrigen nicht eigens als willkürlich gerügt wird.
5.3.2 Sodann beanstandet der Beschwerdeführer, dass im Gutachten E._ ein hypothetischer Mietertragswert von monatlich Fr. 500.-- berücksichtigt wurde. Der Raum, welchen der Gutachter mit dem hypothetischen Wert anvisiert habe, sei zu tief und könne nicht vermietet werden, ausserdem bestehe keine Nachfrage nach solchen Räumen.
Aus dem angefochtenen Urteil geht hervor, dass der Beschwerdeführer den Raum gegenwärtig seiner eigenen Firma zur Verfügung stellt und dafür in seiner Steuererklärung einen Mietertrag von jährlich Fr. 6'000.-- ausgewiesen hat. Der Raum kann also durchaus genutzt werden und es ist nicht willkürlich, wenn die Vorinstanz diese Tatsache berücksichtigt bzw. keine entsprechende Abweichung vom Gutachten E._ vorgenommen hat.
5.3.3 Schliesslich rügt der Beschwerdeführer, es hätte bereits deshalb auf das Gutachten F._ abgestützt werden müssen, weil dieses die Marktverhältnisse realistischer beurteile und es zudem die aktuellere Schatzung sei, was insbesondere bezüglich Sanierungsbedarf, der sich wegen den hohen Trennungskosten aufgestaut habe, relevant sei.
Die beiden Gutachten ergingen innerhalb gut eines Jahres, so dass allfällige konjunkturelle Mehrwerte (Minderwerte wären angesichts der steigenden Liegenschaftspreise ohnehin nicht ersichtlich) unerheblich sind. In diesem Zusammenhang ist keine Willkür ersichtlich, wenn die Vorinstanz auf das Gutachten E._ abgestellt hat. Zum angeblich aufgelaufenen Sanierungsbedarf ergeben sich weder aus dem angefochtenen Urteil noch aus den Ausführungen des Beschwerdeführers konkrete Anhaltspunkte. Mit der nicht weiter belegten Behauptung ist ebenfalls keine Willkür darzutun. Schliesslich ergibt sich auch daraus keine Willkür, dass die Vorinstanz grundsätzlich das von den Parteien gemeinsam in Auftrag gegebene Gutachten der vom Beschwerdeführer (nach Bekanntsein des ersten Gutachtens) einseitig in Auftrag gegebenen Schätzung vorzog.
5.4 Aus den dargelegten Gründen ist die Beschwerde abzuweisen, soweit darauf eingetreten werden kann.
6. Entsprechend dem Ausgang des Verfahrens sind die Gerichtskosten dem Beschwerdeführer aufzuerlegen (<ref-law>) und er hat die Beschwerdegegnerin für die Stellungnahme zum Gesuch um aufschiebende Wirkung zu entschädigen (<ref-law>).
Wie sich aus den vorstehenden Erwägungen ergibt, war die Beschwerde von Anfang an aussichtslos. Das Gesuch des Beschwerdeführers um unentgeltliche Rechtspflege ist somit abzuweisen (<ref-law>). Das Gesuch der Beschwerdegegnerin um unentgeltliche Rechtspflege wird infolge der zugesprochenen Entschädigung gegenstandslos (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Das Gesuch des Beschwerdeführers um unentgeltliche Rechtspflege wird abgewiesen.
3. Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdeführer auferlegt.
4. Der Beschwerdeführer hat die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 500.-- zu entschädigen.
5. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Solothurn, Zivilkammer, schriftlich mitgeteilt.
Lausanne, 17. April 2013
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: von Werdt
Die Gerichtsschreiberin: Friedli-Bruggmann