Sachverhalt:
A. Der Einzelrichter am Bezirksgericht Zürich verurteilte X._ am 14. Dezember 2007 wegen mehrfacher Widerhandlung gegen Art. 23a in Verbindung mit Art. 13e des Bundesgesetzes vom 26. März 1931 über Aufenthalt und Niederlassung der Ausländer (ANAG; BS 1 121, AS 1995 146), begangen durch Missachtung einer Ausgrenzungsverfügung, sowie wegen Hinderung einer Amtshandlung nach <ref-law> zu sechs Monaten unbedingt vollziehbarer Freiheitsstrafe, teilweise als Zusatzstrafe zum Strafbefehl des Juge d'instruction de Lausanne vom 5. April 2005 und zum Urteil des Obergerichts des Kantons Zürich vom 18. Mai 2006, durch welche er zu unbedingt vollziehbaren Gefängnisstrafen von drei respektive vier Monaten verurteilt worden war. X._ erklärte Berufung, die sich ausschliesslich gegen die Sanktion richtete.
Das Obergericht des Kantons Zürich, II. Strafkammer, stellte mit Urteil vom 28. April 2009 fest, dass das Urteil des Einzelrichters am Bezirksgericht Zürich vom 14. Dezember 2007 hinsichtlich Schuldspruch und Kostenaufstellung in Rechtskraft erwachsen war, und bestrafte X._ in Bestätigung des erstinstanzlichen Entscheids mit einer unbedingt vollziehbaren Freiheitsstrafe von sechs Monaten.
B. Mit Beschwerde in Strafsachen vom 19. August 2009 beantragt X._, das Urteil des Obergerichts vom 28. April 2009 sei aufzuheben, und die Sache sei zur erneuten Beurteilung an das Obergericht zurückzuweisen. Er ersucht um unentgeltliche Rechtspflege und Verbeiständung.
C. Vernehmlassungen wurden keine eingeholt.

Erwägungen:
1. Die Bestimmungen des Allgemeinen Teils des Strafgesetzbuchs wurden durch das Bundesgesetz vom 13. Dezember 2002 teilweise revidiert. Das neue Recht trat am 1. Januar 2007 in Kraft. Zudem trat am 1. Januar 2008 das neue Bundesgesetz vom 16. Dezember 2005 über die Ausländerinnen und Ausländer (AuG; SR 142.20) in Kraft, welches das ANAG ersetzt. Es ist einerseits der neue Allgemeine Teil des Strafgesetzbuchs und andererseits das ANAG als das im konkreten Fall mildere Recht anzuwenden.
2. 2.1 Der Beschwerdeführer macht geltend, die Vorinstanz verneine zu Unrecht eine Verletzung des Beschleunigungsgebots im Sinne von Art. 6 Ziff. 1 EMRK sowie <ref-law>. Das Strafverfahren habe insgesamt und in einzelnen Abschnitten übermässig lange gedauert, weshalb die Strafe zu mildern sei. Die Feststellungen der Vorinstanz zur Dauer des Verfahrens seien aktenwidrig und unvollständig. Die zweimalige längere Untätigkeit der Untersuchungsbehörde sowie die übermässig lange Dauer des erstinstanzlichen Verfahrens könnten diesen nicht entnommen werden. Zudem äussere sich die Vorinstanz nicht zur insgesamt aussergewöhnlich langen Dauer des Verfahrens, wodurch sie auch ihre Begründungspflicht verletze.
2.2 Das in <ref-law>, Art. 6 Ziff. 1 EMRK und Art. 14 Ziff. 3 lit. c UNO-Pakt II festgeschriebene Beschleunigungsgebot verpflichtet die Behörden, das Strafverfahren voranzutreiben, um den Beschuldigten nicht unnötig über die gegen ihn erhobenen Vorwürfe im Ungewissen zu lassen. Welche Verfahrensdauer angemessen ist, hängt von den Umständen des Einzelfalls ab, die in ihrer Gesamtheit zu würdigen sind. Von den Behörden und Gerichten kann nicht verlangt werden, sich ständig einem einzigen Fall zu widmen. Deshalb sowie aus Gründen wie faktischer und prozessualer Schwierigkeiten sind Zeiten, in denen das Verfahren stillsteht, unumgänglich. Wenn keiner dieser Zeitabschnitte stossend wirkt, ist eine Gesamtbetrachtung vorzunehmen. Zeiten mit intensiver behördlicher oder gerichtlicher Tätigkeit können andere Zeitspannen kompensieren, in denen aufgrund der Geschäftslast keine Verfahrenshandlungen erfolgten. Wird eine Verletzung des Beschleunigungsgebotes festgestellt, ist diesem Umstand angemessen Rechnung zu tragen. Dabei ist einerseits zu berücksichtigen, wie schwer der Beschuldigte durch die Verfahrensverzögerung getroffen wurde, andererseits aber auch, wie gravierend die ihm vorgeworfenen Straftaten sind und welche Strafe ausgesprochen werden müsste, wenn keine Verletzung des Beschleunigungsgebotes vorläge. Rechnung zu tragen ist den Interessen der Geschädigten und der Komplexität des Falls. Ebenso ist in Betracht zu ziehen, wer die Verfahrensverzögerung zu vertreten hat. Das Gericht ist verpflichtet, die Verletzung des Beschleunigungsgebotes ausdrücklich festzuhalten und gegebenenfalls darzulegen, in welchem Ausmass es diesen Umstand berücksichtigt hat (<ref-ruling> E. 8 S. 170; <ref-ruling> E. 3 S. 54 ff.; <ref-ruling> E. 2a S. 140 f.; <ref-ruling> E. 3 und 4 S. 126 ff.; Urteil des Bundesgerichts 6B_440/2008 vom 11.11.2008 E. 6.1; Hans Wiprächtiger, in: Basler Kommentar, Strafrecht, 2. Aufl. 2007, N. 137 zu <ref-law>).
Aus dem in <ref-law> garantierten Anspruch auf rechtliches Gehör folgt die Pflicht der Behörde, ihren Entscheid zu begründen. Die Begründung muss so abgefasst sein, dass der Betroffene den Entscheid gegebenenfalls sachgerecht anfechten kann. Sie muss kurz die wesentlichen Überlegungen nennen, von denen sich das Gericht hat leiten lassen und auf die sich sein Entscheid stützt. Nicht erforderlich ist hingegen, dass sich der Entscheid mit allen Parteistandpunkten einlässlich auseinandersetzt und jedes einzelne Vorbringen ausdrücklich widerlegt (<ref-ruling> E. 3.1 S. 277; <ref-ruling> E. 3.3 S. 445; je mit Hinweisen).
2.3 Die Vorinstanz verneint eine Verletzung des Beschleunigungsgebots. Der Beschwerdeführer sei seit Eröffnung der Strafuntersuchung im April 2005 immer wieder (letztmals am 16. März 2007) verhaftet worden, sodass es stets zur Eröffnung neuer Nebendossiers gekommen sei. Das erstinstanzliche Urteil sei neun Monate nach der letzten Verhaftung und der zweitinstanzliche Entscheid innert Jahresfrist nach Erklärung der Berufung ergangen.
2.4 Diese Erwägungen der Vorinstanz sind zwar knapp, genügen aber den sich aus der Bundesverfassung ergebenden Begründungsanforderungen, zumal die Vorinstanz auf die Akten verweist, aus welchen der Beschwerdeführer erkennen kann, weshalb sie eine Verletzung des Beschleunigungsgebots verneint. Der Beschwerdeführer ist denn auch durchaus in der Lage, das vorinstanzliche Urteil in diesem Punkt anzufechten.
2.5 Am 3. April 2005 betrat der Beschwerdeführer das Gebiet der Stadt Zürich in Missachtung der Verfügung des Migrationsamts des Kantons Zürich vom 20. August 2004, mit welcher ihm das Betreten des Gebiets der Stadt Zürich und ein Aufenthalt in diesem Gebiet auf unbestimmte Zeit untersagt worden war. Die Strafuntersuchung gegen den Beschwerdeführer wegen Widerhandlung gegen Art. 23a i.V.m. Art. 13e ANAG wurde noch am selben Tag eröffnet. Die weiteren zu beurteilenden, gleichartigen Widerhandlungen gegen das ANAG verübte der Beschwerdeführer am 30. April 2006 und am 28. November 2006, wobei er sich anlässlich des letzten Vorfalls zudem der polizeilichen Kontrolle durch Flucht zu entziehen versuchte. Gegenstand des kantonalen Strafverfahrens bildeten somit der Vorwurf der dreifachen Widerhandlung gegen das ANAG und der Vorwurf der Hinderung einer Amtshandlung. Die Schlusseinvernahme erfolgte am 30. November 2006, am 16. März 2007 kam es zur letzten Verhaftung des Beschwerdeführers, und am 18. April 2007 wurde Anklage erhoben. Die erstinstanzliche Hauptverhandlung fand am 13. September 2007 statt. Das erstinstanzliche Urteil erging am 14. Dezember 2007 und wurde am 10. April 2008 in nicht begründeter Ausfertigung zugestellt. Am 21. April 2008 erklärte der Beschwerdeführer Berufung. Das vollständig begründete erstinstanzliche Urteil ging am 19. September 2008 bei der Vertreterin des Beschwerdeführers ein. Nachdem der Beschwerdeführer seine Beanstandungen benannt hatte, die Entschädigung der amtlichen Verteidigerin festgesetzt und von der Staatsanwaltschaft die Bestätigung des erstinstanzlichen Urteils beantragt worden war, wurden mit Verfügung vom 5. Dezember 2008 die Akten der Vorinstanz zur Behandlung der Berufung zugestellt. Am 28. April 2009 erging das vorinstanzliche Urteil, das am 18. Juni 2009 in vollständiger Ausfertigung zugestellt wurde.
2.6 Die gesamte Verfahrensdauer von rund vier Jahren hinsichtlich der Widerhandlung gegen das ANAG vom 3. April 2005 bis zum Zeitpunkt der Zustellung des vorinstanzlichen Urteils ist unter den gegebenen Umständen nicht übermässig. Im Hinblick auf die weiteren hier zu beurteilenden Widerhandlungen gegen das ANAG beträgt die Verfahrensdauer ca. drei respektive ca. zweieinhalb Jahre. Es ist zu berücksichtigen, dass es seit Beginn des Verfahrens zu neuen Straftaten, Verfahrenseinstellungen, weiteren Verurteilungen und Gefängnisaufenthalten des Beschwerdeführers kam, und dass dieser unter verschiedenen Namen aufzutreten pflegte, womit die Übersichtlichkeit und beförderliche Erledigung erschwert wurde. Schliesslich stand mehrmals die Ausweisung des Beschwerdeführers im Raum, was einen direkten Einfluss auf die Beurteilung des vorliegenden Falls hatte. Nach Art. 13e i.V.m. Art. 23a ANAG kann nämlich, wer Massnahmen nach Art. 13e ANAG nicht befolgt, nur bestraft werden, wenn der Vollzug der Weg- oder Ausweisung aus rechtlichen oder tatsächlichen Gründen undurchführbar ist.
2.7 Zum Vorwurf der Untätigkeit der Staatsanwaltschaft während achteinhalb Monaten nach Eröffnung der Strafuntersuchung vom 3. April 2005 ist Folgendes anzumerken: Kurz vor der Anhebung der Strafuntersuchung hatte die Staatsanwaltschaft Zürich-Sihl am 2. März 2005 in einer anderen Angelegenheit Anklage wegen Missachtung einer Ausgrenzung erhoben. Am 15. August 2005 fällte das Bezirksgericht Zürich das Urteil, wogegen der Beschwerdeführer Berufung erklärte, über welche das Obergericht am 18. Mai 2006 entschied. Der Beschwerdeführer hielt sich zudem im fraglichen Zeitraum teilweise im Strafvollzug auf. Die Untätigkeit der Strafverfolgungsbehörden lässt sich unter anderem damit erklären und rechtfertigen, dass der Beschwerdeführer ohnehin andere unbedingt vollziehbare Freiheitsstrafen wegen Widerhandlungen gegen das ANAG zu verbüssen hatte beziehungsweise die Ausfällung solcher Strafen zu erwarten war (3 Monate Gefängnis gemäss Strafbefehl der Bezirksanwaltschaft Zürich vom 18. Dezember 2004, 3 Monate Gefängnis gemäss Strafbefehl des Juge d'instruction de Lausanne vom 5. April 2005 und 4 Monate Gefängnis gemäss Urteil des Bezirksgerichts Zürich vom 15. August 2005 beziehungsweise Urteil des Obergerichts des Kantons Zürich vom 18. Mai 2006). Schliesslich stand seine Ausschaffung beziehungsweise Ausreise nach Algerien zur Debatte (vgl. E. 2.6 hievor). Es ist offensichtlich, dass mehrere gleichzeitig geführte Verfahren zu einer Verkomplizierung der Abläufe führen, und die Strafverfolgungsbehörden daher unter bestimmten Umständen einen Schritt in einem anderen Verfahren abwarten. Auch wenn die Behandlung der Vorwürfe gegen den Beschwerdeführer im vorliegenden Verfahren nicht als besonders schwierig oder aufwendig zu bezeichnen ist, kann unter Berücksichtigung der konkreten Umstände nicht von einer ungebührlichen Verzögerung des Verfahrens gesprochen werden.
Der Zeitablauf zwischen der Schlusseinvernahme vom 30. November 2006 und der Anklageerhebung vom 18. April 2007 ist nicht übermässig lange und stellt keine relevante Verfahrensverzögerung dar.
Das erstinstanzliche Verfahren dauerte von der Anklageerhebung am 18. April 2007 bis zur Zustellung des 21 Seiten umfassenden schriftlich begründeten Urteils am 19. September 2008 ein Jahr und fünf Monate. Das ist verhältnismässig lange, zumal die Beurteilung der Gegenstand des Verfahrens bildenden Vorwürfe weder in tatsächlicher noch in rechtlicher Hinsicht besondere Schwierigkeiten bot. Allerdings wurde das erstinstanzliche Urteil, das nach Durchführung der Hauptverhandlung vom 13. September 2007 am 14. Dezember 2007 ausgefällt wurde, dem Beschwerdeführer am 10. April 2008 in nicht begründeter Ausfertigung zugestellt, wodurch der Beschwerdeführer knapp ein Jahr nach der Anklageerhebung und ein Jahr und fünf Monate nach den letzten Gegenstand des Verfahrens bildenden Taten vom 28. November 2006 Kenntnis vom Urteilsdispositiv erhielt und somit nicht mehr im Ungewissen war. Zudem konnte das erstinstanzliche Urteil nicht unmittelbar im Anschluss an die erstinstanzliche Hauptverhandlung gefällt werden, da der Eingang der vollständigen Akten des Migrationsamts abzuwarten war. Weiter war die Rechtsvertreterin des Beschwerdeführers vom 28. Januar 2008 bis 3. März 2008 ferienabwesend. Das erstinstanzliche Verfahren weist somit zwar gewisse Längen auf, doch liegt darin keine eigentliche Verfahrensverschleppung. Dabei darf auch berücksichtigt werden, dass in der Folge das Berufungsverfahren auffallend zügig durchgeführt wurde, wodurch die Länge des erstinstanzlichen Verfahrens kompensiert wurde.
Der Beschwerdeführer zitiert ein Urteil des Obergerichts des Kantons Zürich vom 4. Mai 2009 in Sachen B.S., in welchem festgehalten wird, dass eine Dauer von knapp einem Jahr zwischen der erstinstanzlichen Hauptverhandlung und der Zustellung des begründeten, 23 Seiten umfassenden Urteils eine übermässige Länge darstelle, die in erheblichem Masse strafmindernd zu berücksichtigen sei. Zudem führt er aus, das Bundesgericht habe kürzlich erwogen, dass bei einer fünfjährigen Verfahrensdauer in einer ziemlich aufwendigen Strafuntersuchung eine leichte Minderung der Strafe vorzunehmen sei. Da die Angemessenheit der Verfahrensdauer von den Umständen des Einzelfalls abhängt, kann der Beschwerdeführer aus jenen zeitlichen Gegebenheiten nichts direkt für sich ableiten.
2.8 Zusammenfassend nahmen weder die Gesamtheit noch die einzelnen Abschnitte des Verfahrens übermässig viel Zeit in Anspruch. Das Beschleunigungsgebot wurde vorliegend nicht verletzt.
3. 3.1 Der Beschwerdeführer rügt eine Verletzung des Verbots der "reformatio in peius". Die Vorinstanz habe im Schuldpunkt hinsichtlich Hinderung einer Amtshandlung (<ref-law>) in Anwendung von <ref-law> wegen Geringfügigkeit von einer Bestrafung abgesehen. Folgerichtig hätte sie die von der ersten Instanz ausgefällte Strafe herabsetzen müssen. Indem sie die erstinstanzliche Strafe bestätigt habe, habe sie das Verschlechterungsverbot verletzt.
3.2 Diese Ausführungen genügen den Anforderungen an die Begründung einer Beschwerde in Strafsachen nicht. Der Beschwerdeführer legt nicht dar, welche Norm die Vorinstanz durch die Bestätigung des erstinstanzlichen Strafmasses in einer Konstellation der vorliegenden Art verletzt haben soll. Das Verbot der "reformatio in peius" ergibt sich weder aus der BV noch aus der EMRK. Es bestimmt sich in einem kantonalen Rechtsmittelverfahren nach dem kantonalen Prozessrecht. Welche Bestimmungen der zürcherischen Strafprozessordnung die Vorinstanz inwiefern willkürlich angewandt hat, legt der Beschwerdeführer nicht dar. Im Übrigen ist es der Berufungsinstanz von Bundesrechts wegen nicht verwehrt, die von der ersten Instanz ausgefällte Strafe zu bestätigen, wenn einer von mehreren Schuldpunkten wegfällt, sofern sie diese Strafe als angemessen erachtet und dies in ihrem Urteil begründet (siehe Urteil des Bundesgerichts 6B_495/2008 vom 27. Dezember 2008 E. 1.4).
Die Beschwerde ist auch in diesem Punkt abzuweisen, soweit darauf einzutreten ist.
4. 4.1 Der Beschwerdeführer macht geltend, die Vorinstanz habe ihm den bedingten Strafvollzug zu Unrecht verweigert. Zwar weise er zahlreiche, teils einschlägige Vorstrafen auf. Er sei aber seit dem 2. Juni 2008 mit einer Schweizer Bürgerin verheiratet. Ein Rekurs gegen die Abweisung seines Gesuchs vom 16. Juli 2008 um Erteilung einer Aufenthaltsbewilligung für den Kanton Zürich sei hängig. Gegen eine Verfügung des Migrationsamts des Kantons Zürich vom 31. Oktober 2008, mit welcher ihm eine Frist zum Verlassen des schweizerischen Staatsgebiets bis zum 31. Januar 2009 gesetzt wurde, habe er ebenfalls Rekurs eingereicht. Diesem komme von Gesetzes wegen aufschiebende Wirkung zu. Somit halte er sich seit der Gesuchsstellung vom 16. Juli 2008 ans Migrationsamt, jedenfalls aber seit der Verfügung des Migrationsamts vom 31. Oktober 2008 legal in der Schweiz auf. Er könne nicht mehr gegen die Bestimmungen des Ausländergesetzes verstossen beziehungsweise rückfällig werden. Es sei daher hinsichtlich Widerhandlungen gegen die Ausländergesetzgebung von einer günstigen Prognose auszugehen. Die Begründung der Vorinstanz sei willkürlich, da alleine auf die Frage abgestellt werde, ob er eine Aufenthaltsbewilligung erhalten werde oder nicht.
4.2 Nach <ref-law> schiebt das Gericht den Vollzug einer Geldstrafe, von gemeinnütziger Arbeit oder einer Freiheitsstrafe von mindestens sechs Monaten und höchstens zwei Jahren in der Regel auf, wenn eine unbedingte Strafe nicht notwendig erscheint, um den Täter von der Begehung weiterer Verbrechen oder Vergehen abzuhalten.
Die Vorinstanz lehnt unter Hinweis auf die vielen und teils einschlägigen Vorstrafen des Beschwerdeführers die Gewährung des bedingten Strafvollzugs ab. Sie verweist auf die einlässlich begründete Auffassung der ersten Instanz, dass eine unbedingte Strafe notwendig sei, um den Beschwerdeführer von der Begehung weiterer Delikte abzuhalten. Zudem erwägt die Vorinstanz, dass sich der Beschwerdeführer auch durch die unbedingte Freiheitsstrafe von vier Monaten, die sie am 18. Mai 2006 wegen Missachtung der Ausgrenzung ausgefällt habe, nicht habe beeindrucken lassen. Vielmehr sei er vier Monate später und am 15. August 2007 erneut auf dem Gebiet der Stadt Zürich angetroffen worden. Das Vorleben und das Verhalten des Beschwerdeführers würden seine Unverbesserlichkeit zeigen und die gesetzliche Vermutung einer günstigen Prognose klar widerlegen. Daran vermöge auch seine Verehelichung nichts Wesentliches zu ändern. Es sei schliesslich ungewiss, ob der Beschwerdeführer eine Aufenthaltsbewilligung erhalten werde.
Die Verweigerung des bedingten Strafvollzugs durch die Vorinstanz ist nicht zu beanstanden. Insbesondere ist im Hinblick auf die Argumentation des Beschwerdeführers festzuhalten, dass der Verurteilte durch die Warnungsstrafe von Verbrechen und Vergehen schlechthin abgehalten werden muss, und nicht nur von Straftaten von der Art, die zur Beurteilung steht. Die Aussicht auf Besserung, die auf bestimmte Delikte beschränkt ist, vermag den bedingten Strafvollzug nicht zu rechtfertigen (<ref-ruling> S. 59 f.; SCHNEIDER/GARRÉ, in: Basler Kommentar, Strafrecht, 2. Aufl. 2007, N. 41 zu <ref-law>). Der Beschwerdeführer ist neben diversen Widerhandlungen gegen das ANAG auch wegen Diebstahls (mehrfach), Erschleichen einer falschen Beurkundung, Widerhandlungen gegen das SVG und Hehlerei vorbestraft. Indem die Vorinstanz eine unbedingt vollziehbare Strafe ausspricht, verletzt sie ihr Ermessen bei der Beurteilung von Tat und Täter nicht und wendet <ref-law> bundesrechtskonform an.
Die Beschwerde ist auch in diesem Punkt abzuweisen.
5. Die Beschwerde ist abzuweisen, soweit darauf einzutreten ist. Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung ist abzuweisen, da die Beschwerde von vornherein aussichtslos war (<ref-law> e contrario).
Bei diesem Verfahrensausgang sind die bundesgerichtlichen Kosten dem Beschwerdeführer aufzuerlegen (<ref-law>). Seinen angespannten finanziellen Verhältnissen ist mit reduzierten Gerichtskosten Rechnung zu tragen.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird abgewiesen.
3. Die Gerichtskosten von Fr. 1'600.-- werden dem Beschwerdeführer auferlegt.
4. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, II. Strafkammer, schriftlich mitgeteilt.
Lausanne, 17. November 2009
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Favre Häne