Sachverhalt: A. X._ und Z._ lebten im Jahr 2004 in einer nichtehelichen Partnerschaft. Am 4. September 2004 gebar Z._ einen Sohn (Y._), den X._ am 7. Oktober 2004 vor dem Zivilstandsamt anerkannte. Mit Klage vom 9. Juni 2010 gegen Y._ focht X._ die Kindesanerkennung an. Zudem beantragte er die Gewährung der unentgeltlichen Rechtspflege sowie die Beiordnung einer unentgeltlichen Rechtsbeiständin. B. Mit Verfügung vom 17. Juni 2010 wies die Amtsgerichtspräsidentin des Richteramtes Olten-Gösgen das Gesuch um unentgeltliche Rechtspflege und Verbeiständung für das Verfahren auf Anfechtung der Kindesanerkennung ab. Den dagegen von X._ erhobenen Rekurs wies das Obergericht des Kantons Solothurn mit Urteil vom 2. Dezember 2010 ebenso ab (Ziff. 1 des Dispositivs) wie sein Gesuch um unentgeltliche Verbeiständung für das (kostenlose) Rekursverfahren (Ziff. 2 des Dispositivs). C. Dem Bundesgericht beantragt X._ (nachfolgend Beschwerdeführer) in seiner Beschwerde in Zivilsachen vom 19. Januar 2011 die Aufhebung des obergerichtlichen Urteils und die Gewährung der unentgeltlichen Rechtspflege (und Verbeiständung) für das Verfahren vor der Amtsgerichtspräsidentin (nachfolgend Beschwerdegegnerin) sowie die Beiordnung einer unentgeltlichen Rechtsbeiständin für das Rekursverfahren vor dem Obergericht. Zudem stellt er für das bundesgerichtliche Verfahren ein Gesuch um unentgeltliche Rechtspflege und Verbeiständung und verlangt die Gewährung der aufschiebenden Wirkung. Die Beschwerdegegnerin und das Obergericht haben auf eine Stellungnahme zum Gesuch um aufschiebende Wirkung verzichtet. Mit Verfügung vom 28. Januar 2011 hat die Abteilungspräsidentin der Beschwerde die aufschiebende Wirkung zuerkannt. In der Sache beantragt das Obergericht in seiner Vernehmlassung vom 21. Februar 2011 - wie auch die Beschwerdegegnerin in ihrer Vernehmlassung vom 25. Februar 2011 - die Abweisung der Beschwerde. 