Sachverhalt:
A. Die Ehegatten M._ und F._ führten vor dem Richteramt R._ ein Eheschutzverfahren durch. Mit Urteil vom 31. März 2004 stellte die ausserordentliche Gerichtsstatthalterin die beiden Kinder A._ (geboren 1990) und B._ (geboren 1993) unter die Obhut der Mutter. Die monatlichen Unterhaltsbeiträge wurden auf je Fr. 750.-- für die beiden Kinder (ab dem 1. Dezember 2003; exklusive Kinderzulagen) sowie auf Fr. 1'635.-- (vom 1. Dezember 2003 bis zum 31. März 2004), resp. Fr. 1'240.-- (vom 1. April 2004 bis zum 30. November 2004) bzw. Fr. 1'715.-- (ab dem 1. Dezember 2004) für die Ehefrau festgelegt.
B. Die vom Ehegatten gegen diesen Entscheid eingereichte Abänderungsklage wurde mit Urteil vom 6. Dezember 2005 teilweise gutgeheissen. Der Unterhaltsbeitrag an die Ehegattin wurde mit Wirkung ab dem 1. Oktober 2005 auf Fr. 1'475.-- herabgesetzt. Gegen diesen Abänderungsentscheid erhob der Ehegatte Rekurs an das Obergericht des Kantons Solothurn (Rekurs I). Mit Verfügung der Gerichtspräsidentin vom 24. März 2006 wurde das Kind A._ unter die Obhut des Vaters gestellt. Aufgrund dieser Obhutsumteilung verfügte die Gerichtspräsidentin am 22. Mai 2006, dass der Unterhaltsbeitrag für das Kind A._ mit Wirkung ab dem 1. April 2006 aufgehoben und dass ab demselben Datum derjenige für die Ehegattin auf Fr. 750.-- reduziert werde. Auch gegen diesen Entscheid rekurrierte der Ehemann an das Obergericht des Kantons Solothurn (Rekurs II). Mit Urteil vom 19. Oktober 2006 hiess das Obergericht die beiden Rekurse teilweise gut und änderte unter anderem die Unterhaltsbeiträge an die Ehegattin dergestalt ab, dass für den Monat Oktober 2005 Fr. 1'475.-- und ab dem 1. November 2005 noch Fr. 650.-- geschuldet sind.
C. Mit Eingabe vom 23. November 2006 führt M._ (fortan: Beschwerdeführer) staatsrechtliche Beschwerde wegen Verletzung der Art. 9 und 29 Abs. 2 BV und verlangt, Ziffer 4 des obergerichtlichen Urteils vom 19. Oktober 2006, eventualiter das gesamte Urteil, aufzuheben.
Ausserdem begehrt der Beschwerdeführer um unentgeltliche Rechtspflege. Zur Sache sind keine Vernehmlassungen eingeholt worden.

Das Bundesgericht zieht in Erwägung:
1. 1.1 Der angefochtene Beschluss ist am 19. Oktober 2006 ergangen, womit auf das vorliegende Verfahren noch die Bestimmungen des Bundesrechtspflegegesetzes (OG) anwendbar sind, ungeachtet des Inkrafttretens des Bundesgesetzes über das Bundesgericht (BGG) am 1. Januar 2007 (vgl. <ref-law>).
1.2 Das Bundesgericht prüft von Amtes wegen und mit freier Kognition, ob und in welchem Umfang auf eine staatsrechtliche Beschwerde einzutreten ist (<ref-ruling> E. 1 S. 156; <ref-ruling> E. 2 S. 250).
1.3 Das Bundesgericht hat wiederholt entschieden, dass kantonal letztinstanzliche Entscheide, in denen Eheschutzmassnahmen angeordnet werden, nicht mit Berufung angefochten werden können. Das Urteil des Obergerichts betreffend Eheschutz (Abänderung von Unterhaltsbeiträgen gemäss <ref-law>) ist kantonal letztinstanzlich und Endentscheid im Sinne von Art. 86 OG, gegen welchen gemäss ständiger Rechtsprechung einzig die staatsrechtliche Beschwerde als subsidiäres Rechtsmittel zulässig ist (Art. 84 Abs. 2 OG; <ref-ruling> E. 2a S. 476 mit Hinweisen). Die staatsrechtliche Beschwerde ist, abgesehen von hier nicht zutreffenden Ausnahmen, rein kassatorischer Natur, das heisst sie kann nur zur Aufhebung des angefochtenen Entscheides führen. Soweit der Beschwerdeführer mehr als die Aufhebung des angefochtenen Urteils verlangt, ist darauf nicht einzutreten (<ref-ruling> E. 1b S. 107; <ref-ruling> E. 5a S. 96 je mit Hinweisen). Der Beschwerdeführer ficht Ziffer 4 des obergerichtlichen Urteils, eventualiter das gesamte Urteil an. Entgegen der Auffassung des Beschwerdeführers hat jedoch der Umfang der Anfechtung mit der kassatorischen Natur der staatsrechtlichen Beschwerde nichts zu tun (vgl. <ref-ruling> E. 1.2.1 S. 131). Demnach tritt das Bundesgericht lediglich auf den (Haupt-) Antrag des Beschwerdeführers auf Aufhebung von Ziffer 4 des obergerichtlichen Urteils ein und dabei nur in dem Umfange, in welchem die Aufhebung begehrt wird.
1.4 Nach Art. 90 Abs. 1 lit. b OG hat sich ein Beschwerdeführer mit den Erwägungen des angefochtenen Entscheides auseinander zu setzen und im Einzelnen darzustellen, worin die Verletzung der angerufenen Verfassungsrechte bestehen soll. Im Verfahren der staatsrechtlichen Beschwerde prüft das Bundesgericht nur klar und detailliert (und damit rechtsgenüglich) erhobene und, soweit möglich, belegte Rügen (<ref-ruling> E. 1.3 S. 261 mit Hinweisen). Neue rechtliche oder tatsächliche Vorbringen und neue Beweismittel (Nova) können - von hier nicht zutreffenden Ausnahmen abgesehen - nicht vorgebracht werden (<ref-ruling> E. 3 S. 57). Des Weiteren werden Ausführungen zum Sachverhalt, welche nicht mit einer konkreten (Willkür-) Rüge verbunden sind, im staatsrechtlichen Beschwerdeverfahren nicht berücksichtigt. Berücksichtigt wird im vorliegenden Verfahren demnach ausschliesslich der vom Beschwerdeführer am 6. Juni 2006 erhobene Rekurs (Rekurs II) und damit die in demselben erwähnten Belege. In diesem Zusammenhang gilt es zu erwähnen, dass es nicht zur Aufgabe des Bundesgerichts gehört, die in der Beschwerdeschrift erwähnten Schreiben und Berichte aus den kantonalen Akten herauszusuchen und dem jeweiligen Verfahren (Rekurs I oder II) zuzuordnen. Auch nimmt das Bundesgericht im Verfahren der Verfassungsbeschwerde keine Beweise wie z. B. eine Parteibefragung ab. Schliesslich tritt das Bundesgericht auf ungenügend begründete Vorbringen und rein appellatorische Kritik am angefochtenen Entscheid, wie sie allenfalls im Rahmen eines Berufungsverfahrens zulässig ist, nicht ein (<ref-ruling> E. 2a S. 3; <ref-ruling> E. 1b S. 495; <ref-ruling> E. 1.5 S. 297).
Wirft der Beschwerdeführer - wie vorliegend - der kantonalen Instanz zur Hauptsache Willkür vor, so hat er aufzuzeigen, inwiefern deren Entscheid offensichtlich unhaltbar sein soll, d.h. mit der tatsächlichen Situation in klarem Widerspruch stehe, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletze oder sonst wie in stossender Weise dem Gerechtigkeitsgedanken zuwiderlaufe. Das Bundesgericht greift im Übrigen nur ein, wenn nicht bloss die Begründung des Entscheides, sondern auch das Ergebnis unhaltbar ist (<ref-ruling> E. 1.3 S. 261; <ref-ruling> E. 5.1 S. 17 mit Hinweisen).
2. 2.1 Das Obergericht hat festgehalten, dass der Ehegattin der volle Grundbetrag von Fr. 1'250.-- anzurechnen ist. Des Weiteren ist das Obergericht zum Schluss gelangt, dass die Beschwerdegegnerin mit ihrem Sohn im Hause ihres Lebenspartners wohnt und diesem einen monatlichen Mietzins (inkl. Nebenkosten) von Fr. 1'200.-- bezahlt. Dabei hat es sich im Wesentlichen auf den im Recht liegenden Mietvertrag vom 21. Dezember 2005 (gültig ab dem 1. Februar 2006) zwischen der Beschwerdegegnerin und ihrem neuen Lebenspartner sowie auf die Parteiaussagen gestützt.
2.2 Der Beschwerdeführer rügt diese obergerichtliche Unterhaltsberechnung als willkürlich. Der Beschwerdegegnerin seien nur rund der halbe Grundbetrag in der Höhe von Fr. 775.-- sowie ein Wohnkostenanteil von ca. Fr. 650.-- monatlich bei der Bedarfsberechnung anzurechnen. Dies begründet er damit, dass die Beschwerdegegnerin mit ihrem neuen Lebenspartner im Konkubinat lebe, da jene mit diesem in einer gemeinsamen Wohnung wohne.
2.2 Der Beschwerdeführer rügt diese obergerichtliche Unterhaltsberechnung als willkürlich. Der Beschwerdegegnerin seien nur rund der halbe Grundbetrag in der Höhe von Fr. 775.-- sowie ein Wohnkostenanteil von ca. Fr. 650.-- monatlich bei der Bedarfsberechnung anzurechnen. Dies begründet er damit, dass die Beschwerdegegnerin mit ihrem neuen Lebenspartner im Konkubinat lebe, da jene mit diesem in einer gemeinsamen Wohnung wohne.
2.3 2.3.1 Ein (qualifiziertes) Konkubinat im Sinne der Rechtsprechung ist von der blossen Wohn- und Lebensgemeinschaft zu unterscheiden. Gemäss ständiger Bundesgerichtspraxis ist ein solches Konkubinat erst gegeben, wenn ein der Ehe ähnlicher Unterstützungswille (analog zu <ref-law>) der Lebenspartner besteht. Dies beurteilt sich nach dem umfassenden Beistand, den die Partner sich zu leisten bereit sind. Ob sie die finanziellen Mittel dazu überhaupt aufweisen, ist hingegen unerheblich. Die Folgen eines qualifizierten Konkubinats unterscheiden sich hier nicht vom Fall der Wiederverheiratung der unterhaltsberechtigten Partei, die ihren Anspruch selbst dann verliert, wenn der neue Ehepartner ihr nicht die gleiche Lebenshaltung bieten kann, wie es der bisherige Ehepartner getan hat (vgl. dazu die auch unter dem neuen Scheidungsrecht geltenden <ref-ruling> E. 3a S. 237 und 124 III 52 E. 2 a/aa S. 54 mit Hinweisen; Hausheer/Spycher, Unterhalt nach neuem Scheidungsrecht, 2001, Rz. 10.30c und e). Der Gesetzgeber hat es im Rahmen der Revision des Scheidungsrechts klar abgelehnt, das Konkubinat der unterhaltsberechtigten Partei nur dann in Betracht zu ziehen, insofern es mit wirtschaftlichen Vorteilen verbunden sei. Ein solches Konkubinat führte somit zur Aufhebung oder Sistierung der Unterhaltsrente (Urteil des Bundesgerichts 5C.93/2006 vom 23. Oktober 2006, E. 2.2.1 mit Hinweisen auf die Materialien). Dagegen bringt die (einfache) Wohn- und Lebensgemeinschaft bloss reduzierte Lebenshaltungskosten für die Beteiligten mit sich, die weder zur Sistierung noch zur Aufhebung einer bestehenden Unterhaltsleistung führen, diese jedoch im Rahmen der Bedarfsberechnung abändern können.
Dass ein (qualifiziertes) Konkubinat im Sinne der oberwähnten Grundsätze bestehe, geht weder aus den obergerichtlichen Feststellungen hervor noch lässt sich dies der Beschwerdeschrift entnehmen (Art. 90 Abs. 1 lit. b OG).
2.3.2 Das Obergericht hat weder eine Bedarfsberechnung erstellt noch einen Notbedarf für die Beschwerdegegnerin ermittelt. Jedoch hat es festgestellt, dass ein Manko nur unter den kumulativen Voraussetzungen zu vermeiden sei, dass der Beschwerdegegnerin weder ein hypothetisches Einkommen aufgerechnet werden könne noch ein (qualifiziertes) Konkubinat bestehe und so der Bedarf wesentlich verringert wäre. Ersteres hat das Obergericht verneint und wird vom Beschwerdeführer denn auch nicht angefochten. Letzteres hat es ebenfalls verneint, wogegen sich der Beschwerdeführer jedoch zur Wehr setzt. Aus der mit dem Rekurs II angefochtenen Verfügung vom 22. Mai 2006 ergibt sich ein Notbedarf der Beschwerdegegnerin von Fr. 3'400.--. Folgte man nun dem Beschwerdeführer und reduzierte den Grundbetrag der Beschwerdegegnerin auf Fr. 775.-- sowie deren Mietkosten(-anteil) auf Fr. 650.--, so bliebe gleichwohl ein Manko bestehen. Der der Beschwerdegegnerin zustehende Unterhaltsbeitrag berechnete sich somit nach wie vor aus der Differenz zwischen dem Einkommen des Beschwerdeführers und dessen Bedarf (vgl. <ref-ruling> E. 2c S. 70).
Aus dem Gesagten kann gefolgert werden, dass das Obergericht mit seinen Unterhaltsberechnungen im Ergebnis nicht in Willkür verfallen ist (vgl. oben E. 1.4 i. f.).
3. 3.1 Der Beschwerdeführer rügt die Nichtabnahme des von ihm beantragten Augenscheines (bezüglich der Liegenschaft des Lebenspartners der Beschwerdegegnerin) sowie die Nichtberücksichtigung der von ihm offerierten Beweismittel (Auszug aus dem elektronischen Telefonbuch, Bestätigung der Einwohnerkontrolle) als Verletzung seines Anspruchs auf rechtliches Gehör (<ref-law>). Der Beschwerdeführer sieht auch die (Entscheid-) Begründungspflicht als verletzt, welche verlangt, dass die Behörde die Vorbringen des vom Entscheid in seiner Rechtsstellung Betroffenen auch tatsächlich hört, sorgfältig und ernsthaft prüft und in der Entscheidfindung berücksichtigt, was indessen nicht bedeutet, dass sich diese ausdrücklich mit jeder tatbeständlichen Behauptung und jedem rechtlichen Einwand auseinandersetzen muss. Vielmehr kann sie sich auf die für den Entscheid wesentlichen Gesichtspunkte beschränken (<ref-ruling> E. 2b S. 109 mit Hinweisen; <ref-ruling> E. 4.3 S. 540). Diese vom Beschwerdeführer als verletzt gerügte Begründungspflicht gilt als Teilgehalt des Anspruchs auf rechtliches Gehör, begründet jedoch keine über dieses Verfassungsrecht hinausgehenden Garantien.
3.2 <ref-law> gibt der beweisbelasteten Partei einen Anspruch darauf, für rechtserhebliche Sachvorbringen zum Beweis zugelassen zu werden, wenn ihr Beweisantrag nach Form und Inhalt den Vorschriften des kantonalen Rechts entspricht (<ref-ruling> E. 3 S. 157). Soweit der Beschwerdeführer eine Verletzung seines Beweisanspruchs rügt, ist die staatsrechtliche Beschwerde zulässig (Art. 84 Abs. 2 OG; <ref-ruling> E. 4c S. 294), da kein berufungsfähiger Entscheid vorliegt. Der verfassungsmässige Beweisführungsanspruch schliesst vorweggenommene (antizipierte) Beweiswürdigung jedoch nicht aus. Das Sachgericht darf von beantragten Beweisabnahmen absehen und das Beweisverfahren schliessen, wenn es aufgrund bereits abgenommener Beweise seine Überzeugung gebildet hat und ohne Willkür annehmen kann, dass seine Überzeugung durch weitere Beweiserhebungen nicht ändere (<ref-ruling> E. 2.1 S. 428). Entgegen den Ausführungen des Beschwerdeführers ist antizipierte Beweiswürdigung ungeachtet der in Frage stehenden Beweismittel möglich.
3.3 Es trifft im vorliegenden Fall zu, dass das Obergericht die vom Beschwerdeführer beantragten Beweismittel nicht abgenommen hat. Auch liess das Obergericht unerwähnt, dass es im Sinne einer vorweggenommenen Beweiswürdigung von den beantragten Beweisabnahmen abgesehen und das Beweisverfahren geschlossen habe, da es aufgrund der bereits abgenommenen Beweise seine Überzeugung gebildet habe und ohne Willkür annehmen konnte, dass diese Überzeugung durch weitere Beweiserhebungen nicht geändert werde (<ref-ruling> E. 2.1 S. 428). Aufgrund dieses obergerichtlichen Vorgehens und aufgrund der Tatsache, dass der Anspruch auf rechtliches Gehör formeller Natur ist, müsste diese Gehörsverletzung ungeachtet der Erfolgsaussichten der Beschwerde in der Sache selbst grundsätzlich zur Aufhebung des angefochtenen Beschlusses führen (<ref-ruling> E. 4d S. 132 und V 431 E. 3d S. 437; <ref-ruling> E. 2d/bb S. 24; <ref-ruling> E. 3 S. 118).
Nach ständiger Rechtsprechung setzt die staatsrechtliche Beschwerde in der Regel jedoch ein aktuelles und praktisches Rechtsschutzinteresse im Sinne einer Eintretensvoraussetzung voraus (Art. 88 OG; <ref-ruling> E. 4 S. 286). Der Beschwerdeführer muss eine Verletzung in seinen Rechten geltend machen. Dies setzt gemäss ständiger Bundesgerichtspraxis voraus, dass der Beschwerdeführer aktuelle und praktische Interessen wahrnimmt und nicht faktisch irrelevante Rechtsfragen aufwirft (<ref-ruling> E. 1 S. 258). Doch selbst bei einer Gutheissung der staatsrechtlichen Beschwerde aufgrund der Gehörsverletzung und somit bei einer (späteren) Abnahme der strittigen Beweismittel durch die kantonale Instanz änderte sich am Ergebnis nichts, d. h. der Unterhaltsbeitrag wäre nicht herabzusetzen. Das Existenzminimum der Beschwerdegegnerin wird durch die vorhandenen Mittel auch dann nicht gedeckt, wenn die vom Beschwerdeführer verlangten Kürzungen vorgenommen würden. Der Streit drehte sich somit nur noch um die (Entscheid-) Begründung, was jedoch zur Annahme eines rechtsgenüglichen Rechtsschutzinteresses nicht ausreicht.
4. 4.1 Nach dem Gesagten ist die staatsrechtliche Beschwerde abzuweisen, soweit darauf eingetreten werden kann. Bei diesem Ausgang des Verfahrens wird der Beschwerdeführer kostenpflichtig (Art. 156 Abs. 1 OG). Der Beschwerdegegnerin ist jedoch für das bundesgerichtliche Verfahren keine Entschädigung zuzusprechen, da keine Vernehmlassung eingeholt worden ist.
4.2 Das in der Beschwerde mitenthaltene Gesuch des Beschwerdeführers um unentgeltliche Rechtspflege gemäss Art. 152 OG setzt unter anderem voraus, dass seine Begehren nicht als aussichtslos zu qualifizieren sind. Als aussichtslos sind nach der bundesgerichtlichen Praxis Prozessbegehren anzusehen, bei denen die Gewinnaussichten beträchtlich geringer sind als die Verlustgefahren und die deshalb kaum als ernsthaft bezeichnet werden können. Dagegen gilt ein Begehren nicht als aussichtslos, wenn sich Gewinnaussichten und Verlustgefahren ungefähr die Waage halten oder jene nur wenig geringer sind als diese. Massgebend ist, ob eine Partei, die über die nötigen finanziellen Mittel verfügt, sich bei vernünftiger Überlegung zu einem Prozess entschlösse; 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 (vgl. <ref-ruling> E. 4b S. 275; <ref-ruling> E. 2b S. 271 mit Hinweisen). Dabei ist auf die Erfolgschancen insgesamt abzustellen, weshalb die unentgeltliche Rechtspflege auch dann vollumfänglich abzuweisen ist, wenn die Begehren in gewissen Teilpunkten nicht aussichtslos sind. Im vorliegenden Fall ist die staatsrechtliche Beschwerde jedoch als aussichtslos zu qualifizieren, da eine nicht bedürftige Partei die vorliegende staatsrechtliche Beschwerde bei vernünftiger Überlegung nicht eingereicht hätte. Demnach ist das Gesuch des Beschwerdeführers um unentgeltliche Rechtspflege abzuweisen. Indessen rechtfertigen die Umständen des vorliegenden Falles eine Reduktion der Gerichtskosten.

Demnach erkennt das Bundesgericht:
1. Die staatsrechtliche Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Das Gesuch des Beschwerdeführers um unentgeltliche Rechtspflege wird abgewiesen.
3. Die Gerichtsgebühr von Fr. 1'500.-- wird dem Beschwerdeführer auferlegt.
4. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Solothurn, Zivilkammer, schriftlich mitgeteilt.
Lausanne, 20. Juni 2007
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber: