Sachverhalt:
A. Mit Urteil vom 16. November 2010 sprach die II. Strafkammer des Obergerichts des Kantons Zürich X._ des mehrfachen Vergehens gegen das Bundesgesetz über die Ausländerinnen und Ausländer im Sinne von Art. 115 Abs. 1 lit. b AuG schuldig und verurteilte ihn unter Anrechnung der erstandenen Untersuchungshaft von vier Tagen zu einer Freiheitsstrafe von fünf Monaten, als Zusatzstrafe zu der mit Urteil des Obergerichts des Kantons Zürich vom 15. Oktober 2009 ausgesprochenen Geldstrafe von 90 Tagessätzen zu Fr. 30.-- wegen mehrfacher Vergehen und Übertretungen gegen das Betäubungsmittelgesetz. Die von X._ gegen dieses Urteil gerichtete Beschwerde hiess das Bundesgericht teilweise gut, hob das Urteil der II. Strafkammer des Obergerichts auf und wies die Sache zu neuer Entscheidung an dieses zurück. Die teilweise Gutheissung betraf einzig die Strafzumessung. Das Bundesgericht beanstandete, das Obergericht habe eine Freiheitsstrafe als Zusatzstrafe im Sinne von <ref-law> zu einer Geldstrafe als Grundstrafe ausgefällt. Ungleichartige Strafen seien kumulativ zu verhängen, weil das Asperationsprinzip nur greife, wenn mehrere gleichartige Strafen ausgesprochen würden. Die Bildung einer Gesamtstrafe sei bei ungleichartigen Strafen nicht möglich. Sei das Obergericht der Ansicht, es sei eine Freiheitsstrafe zu verhängen, müsse es eine eigenständige Strafe bilden. In diesem Fall habe es hinreichend zu begründen, weshalb es sich für eine Freiheitsstrafe anstelle einer Geldstrafe entscheide (vgl. dazu <ref-ruling> E. 4.2 mit Hinweisen), und gegebenenfalls die Voraussetzungen nach <ref-law> zu berücksichtigen (Verfahren 6B_2/2011 vom 29. April 2011).
Am 19. Oktober 2011 fällte das Obergericht des Kantons Zürich eine unbedingte Freiheitsstrafe von 5 Monaten aus. Es sprach die Freiheitsstrafe als eigenständige Strafe (und nicht als Zusatzstrafe) aus.
B. Gegen dieses Urteil erhebt X._ Beschwerde in Strafsachen. Er beantragt die Aufhebung des angefochtenen Urteils und die Rückweisung der Sache an die Vorinstanz zur neuen Entscheidung. Er ersucht um Gewährung der unentgeltlichen Rechtspflege und Verbeiständung.

Erwägungen:
1. Verfahrensgegenstand bildet einzig die Strafzumessung. Der Beschwerdeführer rügt die Verletzung von Bundesrecht namentlich im Zusammenhang mit der Wahl und Begründung der Sanktionsart und dem Strafmass. Anfechtungsobjekt ist der vorinstanzliche Entscheid vom 19. Oktober 2011. Soweit der Beschwerdeführer das aufgehobene Urteil des Obergerichts vom 16. November 2010 heranzieht, um materielle Bundesrechtswidrigkeiten in Bezug auf die Strafzumessung aufzuzeigen, ist auf die Beschwerde nicht einzutreten.
2. Als Zusatzstrafe zu der mit Urteil des Obergerichts des Kantons Zürich am 15. Oktober 2009 ausgesprochenen Geldstrafe käme vorliegend für die zu beurteilenden mehrfachen Vergehen des Beschwerdeführers gegen das Ausländergesetz nur eine Geldstrafe in Betracht. Die Vorinstanz erachtet gestützt auf die Kriterien der Zweckmässigkeit und der präventiven Effizienz der Strafe einzig eine Freiheitsstrafe für zweckdienlich. Vor diesem Hintergrund bildet sie eine eigenständige Strafe. In Würdigung aller Strafzumessungsfaktoren hält sie an sich eine Freiheitsstrafe von 8 Monaten für schuldangemessen. Aufgrund des Verbots der reformatio in peius müsse es allerdings bereits aus prozessualen Gründen beim Strafmass von fünf Monaten Freiheitsstrafe bleiben. Die Vorinstanz spricht die Strafe unbedingt aus und zeigt auf, weshalb weder eine Geldstrafe noch gemeinnützige Arbeit in Frage kommt (Urteil, S. 19 - 26).
3. Das Bundesgericht hat die Grundsätze der Strafzumessung nach <ref-law> wiederholt dargelegt (<ref-ruling> E. 5.4 ff. mit Hinweisen). Entsprechendes gilt für die Wahl der Sanktionsart (<ref-ruling> E. 4.2.2; <ref-ruling> E. 4.1; je mit Hinweisen) und die Voraussetzungen der Zulässigkeit von kurzen unbedingten Freiheitsstrafen unter sechs Monaten (<ref-ruling> E. 8; <ref-ruling>). Darauf kann verwiesen werden.
4. 4.1 Die Vorinstanz gibt in ihrer Begründung die für sie entscheiderheblichen Kriterien zur Wahl der Strafart an und führt aus, weshalb sie ausschliesslich eine Freiheitsstrafe als zweckdienliche Sanktion erachtet. Sie weist auf die Vorstrafen des Beschwerdeführers hin. Dieser sei schon zweimal zu einer Freiheitsstrafe verurteilt worden (vgl. angefochtenes Urteil, S. 22, 24). Dennoch habe er erneut und einschlägig weiter delinquiert. Er lasse sich von Verurteilungen und dem Vollzug auch unbedingter Strafen offensichtlich nicht abschrecken und manifestiere damit eine Gleichgültigkeit gegenüber ihm auferlegten und drohenden Strafen. Eine Geldstrafe erweise sich unter diesen Umständen als unzweckmässig. Überdies lasse sich eine Freiheitsstrafe auch mit den Auswirkungen auf den Täter und mit dem sozialen Umfeld vereinbaren, da der Beschwerdeführer weder arbeite noch in stabilen Verhältnissen lebe. Vor diesem Hintergrund, insbesondere aber in Anbetracht der einschlägigen Vorstrafen und der Ungerührtheit des Beschwerdeführers gegenüber dem hiesigen Straf- und Vollzugssystem, durfte die Vorinstanz ohne Bundesrechtsverletzung davon ausgehen, dass nicht eine Geldstrafe, sondern nur eine Freiheitsstrafe als angemessene und zweckmässige Sanktion in Frage kommt.
Die Einwände des Beschwerdeführers überzeugen nicht. Aus dem Umstand, dass die Strafbefehlsrichterin seinen rechtswidrigen Aufenthalt vom 16. November 2010 bis 16. April 2011 "lediglich" mit einer Geldstrafe ahndete, kann er in Bezug auf die Wahl der Sanktionsart im vorliegenden Verfahren nichts für sich ableiten (vgl. Strafbefehl vom 17. April 2011; Beschwerde, S. 5). Inwiefern die Kriterien der Zweckmässigkeit und präventiven Effizienz der Strafe zur Begründung der Wahl der Sanktionsform einer "schlichten Nötigungspolitik" das Wort redeten (Beschwerde, S. 3) und nicht stechen würden (Beschwerde, S. 6), ist nicht ersichtlich, umso weniger als es dem Beschwerdeführer nicht objektiv unmöglich war, die Schweiz legal zu verlassen und nach England oder Jamaika auszureisen (Urteil 6B_2/2011 E. 3.2.2). Ebenso wenig ist zu beanstanden, dass im angefochtenen Urteil davon ausgegangen wird, die Lebensumstände des Beschwerdeführers seien nicht stabil und stünden einer Freiheitsstrafe nicht entgegen. Die Vorinstanz durfte berücksichtigen, dass der Beschwerdeführer nicht arbeitet bzw. nicht arbeiten kann, weder über Einkommen/Nothilfe noch Vermögen verfügt, von seiner in England lebenden Ehefrau finanziell unterstützt wird und er hier mit seiner aktuellen Lebenspartnerin zusammenlebt, welche von ihm ein Kind erwartet (Urteil, S. 22). Die zwischenzeitlich erfolgte Geburt des Kindes A._ am 7. September 2011 und der Umstand, dass er es als eigenes anerkennt (Beschwerde, S. 5), vermögen die vorinstanzliche Einschätzung der persönlichen Verhältnisse des Beschwerdeführers nicht in ein anderes Licht zu stellen. Seine per 1. November 2011 erfolgte Registrierung am Wohnsitz seiner Lebenspartnerin und sein Vorsprechen beim Migrationsamt zur Erfassung seiner biometrischen Daten haben als echte Noven ausser Betracht zu bleiben (<ref-law>). Der Beschwerdeführer vermag daraus nichts zu seinen Gunsten abzuleiten. Entsprechendes gilt für sein Vorbringen, eine unbedingte Freiheitsstrafe sei dem Kindswohl abträglich und müsse bei der Wahl der Sanktionsart in Rechnung gestellt werden. Es kann insoweit auf die bundesgerichtliche Rechtsprechung zur Relevanz der familiären Situation im Rahmen der Strafempfindlichkeit hingewiesen werden (vgl. Urteil 6B_470/2009 vom 23. November 2009 E. 2.5 mit zahlreichen Hinweisen).
4.2 Die Vorinstanz fällt in Würdigung aller Strafzumessungskriterien unter Berücksichtigung der reformatio in peius eine Freiheitsstrafe von 5 Monaten aus. Sie setzt sich in ihren Erwägungen mit den wesentlichen schuldrelevanten Komponenten auseinander und würdigt sämtliche Zumessungsgründe zutreffend. Dass sie sich dabei von rechtlich nicht massgeblichen Gesichtspunkten hätte leiten lassen oder wesentliche Gesichtspunkte nicht berücksichtigt hätte, ist nicht ersichtlich. Dass der Beschwerdeführer, wie er geltend macht, "einst über ein Jahr in Ausschaffungshaft" gesessen hat (Beschwerde, S. 6), brauchte die Vorinstanz nicht strafmindernd in Rechnung zu stellen. Nach der bundesgerichtlichen Rechtsprechung bildet die drohende Wegweisung aus der Schweiz grundsätzlich keinen zwingenden Strafzumessungsfaktor (Urteil 6B_203/2010 vom 27. Mai 2010 E. 5.3.3). Entsprechendes gilt für die Ausschaffungshaft, die als ausländerrechtliche Zwangsmassnahme der Sicherstellung des Vollzugs eines Wegweisungsentscheids dient (Art. 76 AuG). Indessen durfte die Vorinstanz zu Ungunsten des Beschwerdeführers massgeblich straferhöhend berücksichtigen, dass dieser auch während des vorliegenden Strafverfahrens erneut einschlägig delinquierte. So wurde der Beschwerdeführer mit Strafbefehl vom 17. April 2011 wegen rechtswidrigen Aufenthalts sowie wegen mehrfacher Übertretung gegen das Betäubungsmittelgesetz mit einer Geldstrafe von 120 Tagessätzen zu je Fr. 30.-- und zu einer Busse von Fr. 300.-- bestraft (Urteil, S. 25). Mit seinen prozessualen Einwendungen gegen den rechtskräftigen Strafbefehl ist der Beschwerdeführer im vorliegenden Verfahren nicht zu hören (vgl. zur Rechtskraft dieses Strafbefehls, act. 2, Beschwerdebeilage 4, Beschluss des Obergerichts des Kantons Zürich vom 31. August 2011, S. 2).
4.3 Der Beschwerdeführer ist der Ansicht, die Vorinstanz begründe die fünfmonatige unbedingte Freiheitsstrafe nicht ausreichend. Seine Meinung legt er nicht näher dar. Wohl wendet das Bundesgericht Bundesrecht von Amtes wegen an (<ref-law>). Das bedeutet jedoch nicht, dass überhaupt nicht zu erörtern wäre, inwiefern der angefochtene Entscheid bundesrechtliche Normen verletzen könnte. Es besteht insoweit eine minimale Rügepflicht (<ref-law>; vgl. Urteil 6B_609/2009 vom 22. Februar 2011 E. 2.2.1). Ob der Beschwerdeführer dieser Pflicht nachkommt, ist fraglich, kann aber letztlich dahingestellt bleiben, weil sein Vorbringen unbegründet ist. Die vorinstanzlichen Erwägungen zu <ref-law> sind zwar eher knapp ausgefallen. Es lässt sich ihnen aber - auch unter Berücksichtigung der im Rahmen von <ref-law> geltenden, erhöhten Anforderungen an die Begründungspflicht - hinlänglich entnehmen, weshalb dem Beschwerdeführer keine günstige Prognose gestellt wird und ein bedingter Strafvollzug im Sinne von <ref-law> entfällt. Die Vorinstanz führt ferner aus, dass und weshalb der Vollzug einer Geldstrafe oder einer Arbeitsstrafe nicht möglich ist und nur eine Freiheitsstrafe als zweckmässige Sanktionsform in Frage kommt (Urteil, S. 25 f.; <ref-ruling> E. 8.4). Die Begründung verletzt unter diesen Umständen kein Bundesrecht.
4.4 Die Beschwerde ist abzuweisen, soweit darauf einzutreten ist. Das Gesuch um unentgeltliche Rechtspflege ist wegen Aussichtslosigkeit der Rechtsbegehren abzuweisen (<ref-law>). Der finanziellen Lage des Beschwerdeführers ist mit herabgesetzten Gerichtskosten Rechnung zu tragen (Art. 65 Abs. 2 und Art. 66 Abs. 1 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Das Gesuch um unentgeltliche Rechtspflege wird abgewiesen.
3. Die Gerichtskosten von Fr. 800.-- werden dem Beschwerdeführer auferlegt.
4. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, II. Strafkammer, schriftlich mitgeteilt.
Lausanne, 3. April 2012
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Mathys
Die Gerichtsschreiberin: Arquint Hill