Sachverhalt:
A. A.a Mit Urteil vom 11. Oktober 2006 sprach das Bezirksgericht Zürich X._ des Raubes, des unvollendet versuchten Betrugs, des betrügerischen Missbrauchs einer Datenverarbeitungsanlage sowie des Hausfriedensbruchs schuldig. Es verurteilte ihn zu 3 Jahren Zuchthaus und ordnete eine ambulante strafvollzugsbegleitende Massnahme an (Art. 43 Ziff. 1 Abs. 1 aStGB).
A.b Die Staatsanwaltschaft des Kantons Zürich und X._ appellierten im Strafpunkt. Mit Urteil vom 18. März 2008 erhöhte das Obergericht des Kantons Zürich die Freiheitsstrafe auf 3 1⁄2 Jahre. Für die Dauer des Strafvollzugs wurde eine ambulante Massnahme nach <ref-law> angeordnet. Das Obergericht lehnte es ab, den Strafvollzug im Sinne von <ref-law> zu Gunsten der ambulanten Behandlung aufzuschieben.
A.c X._ erhob Beschwerde in Strafsachen beim Bundesgericht. Mit Urteil vom 7. Januar 2009 hiess dieses die Beschwerde teilweise gut, hob das Urteil des Obergerichts des Kantons Zürich vom 18. März 2008 auf und wies die Angelegenheit zur neuen Beurteilung an die Vorinstanz zurück.
B. Das Obergericht des Kantons Zürich bestätigte mit Urteil vom 25. Juni 2009 im Ergebnis seinen Schuldspruch. Es bestrafte X._ mit einer Freiheitsstrafe von 3 1⁄2 Jahren und ordnete eine ambulante Massnahme nach <ref-law> während der Dauer des Strafvollzugs an.
C. X._ führt Beschwerde beim Bundesgericht. Er beantragt, der angefochtene Entscheid sei aufzuheben, und die Sache sei im Sinne der Erwägungen zur Neubeurteilung und zur neuen Entscheidung an die Vorinstanz zurückzuweisen. Er beantragt ausserdem die Gewährung der unentgeltlichen Rechtspflege und Verbeiständung.
D. Es wurden keine Vernehmlassungen eingeholt.

Erwägungen:
1. Der Beschwerdeführer verwirkte in den Jahren 2000-2003 verschiedene einschlägige Jugendstrafen. Im Rahmen der Strafzumessung berücksichtigte die Vorinstanz in ihrem Urteil vom 18. März 2008 die Jugendstrafen mangels Eintragung im Strafregister nicht als straferhöhend. Das Bundesgericht wies in seinem Urteil vom 7. Januar 2009 die Vorinstanz an, die einschlägigen Jugendstrafen straferhöhend und die Wiedergutmachungsbemühungen des Beschwerdeführers strafmindernd zu berücksichtigen. Ferner sollte sie die persönliche und berufliche Entwicklung sowie die Beziehungssituation des Beschwerdeführers nach dem aktuellen Stand neu einschätzen und bezüglich Strafmass insgesamt zwar eine tiefere, aber keine höhere als die bisher ausgesprochene 3 1⁄2-jährige Freiheitsstrafe ausfällen dürfen (<ref-ruling> E. 6).
Die Vorinstanz kommt in ihrem neuen Urteil vom 25. Juni 2009 zum Ergebnis, die Neubeurteilung unter Berücksichtigung der bundesgerichtlichen Anweisungen führe zu keinem anderen Strafmass, weshalb sie eine zum ersten Urteil identische Strafsanktion ausfällte.
2. 2.1 Der Beschwerdeführer erachtet die Ausführungen der Vorinstanz, wonach er seit der Berufungsverhandlung bereits zwei Mal die Stelle gewechselt habe und sich nach wie vor in finanziellen Schwierigkeiten befinde, als aktenwidrig bzw. willkürlich. Auch könne keine Rede davon sein, dass er entgegen der impliziten Auffassung der Vorinstanz seine Therapie ohne ersichtlichen Grund abgebrochen und sich nicht aktiv um die Fortsetzung dieser Therapie bemüht habe (Beschwerde, S. 8 f.).
Aktenwidrig sei ferner die Feststellung der Vorinstanz, der Gutachter habe bei ihm ein "hohes vorbestehendes strukturelles Rückfallrisiko" diagnostiziert. Aktenkundlich sei ein "ungünstiges strukturelles Rückfallrisiko" aufgrund der jugendanwaltschaftlichen Vorkommnisse sowie der Anlasstaten. Der Gutachter habe in der Folge differenziert, das Rückfallrisiko sei hinsichtlich Betrugsdelikte und Urkundenfälschungen erheblich, in Bezug auf erneute Aggressionsdelikte jedoch als moderat einzustufen (Beschwerde, S. 10).
2.2 Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat. Die Feststellung des Sachverhalts durch die Vorinstanz kann nur gerügt werden, wenn sie offensichtlich unrichtig, d.h. willkürlich im Sinne von <ref-law> ist (<ref-ruling> E. 1.2.2) oder wenn sie auf einer Verletzung von schweizerischem Recht im Sinne von <ref-law> beruht (<ref-law>). Die Rüge der offensichtlich unrichtigen Feststellung des Sachverhalts prüft das Bundesgericht gemäss <ref-law> nur insoweit, als in der Beschwerde explizit vorgebracht und substantiiert dargelegt wird, inwiefern der Entscheid an einem qualifizierten und offensichtlichen Mangel leidet (<ref-ruling> E. 1.4.3; <ref-ruling> E. 1.3 mit Hinweisen).
2.3 Was der Beschwerdeführer gegen die tatsächlichen Feststellungen der Vorinstanz einwendet, erschöpft sich in einer blossen appellatorischen Kritik am angefochtenen Urteil, die für die Begründung einer willkürlichen Feststellung des Sachverhalts nicht genügt. Seine Ausführungen betreffend Stellenwechsel, finanzielle Schwierigkeiten und Therapieabbruch sind nicht geeignet, offensichtlich erhebliche und schlechterdings nicht zu unterdrückende Zweifel an der vorinstanzlichen Sachverhaltsfeststellung darzutun. Denn für die Begründung von Willkür genügt praxisgemäss nicht, dass das angefochtene Urteil mit der Darstellung des Beschwerdeführers nicht übereinstimmt oder eine andere Lösung oder Würdigung vertretbar erscheint oder gar vorzuziehen wäre (<ref-ruling> nicht publ. E. 4.1; <ref-ruling> E. 2b mit Hinweisen). Auf die Beschwerde ist in diesem Punkt nicht einzutreten.
3. 3.1 Der Beschwerdeführer wendet sich gegen die straferhöhende Berücksichtigung seiner Vorstrafen. Das Bundesgericht habe im Rückweisungsentscheid festgehalten, die Vorinstanz hätte die Vorstrafen in Rechnung stellen sollen. Dieser Strafzumessungsfehler führe für sich genommen jedoch nicht zur Aufhebung des angefochtenen Urteils, zumal das Bundesgericht nicht über die Begehren der Parteien hinausgehen dürfe und die Beschwerdegegnerin hiergegen keine Beschwerde erhoben habe. Trotzdem habe das Bundesgericht die Vorinstanz angewiesen, diesen Strafzumessungsfehler bei der Neubeurteilung straferhöhend zu berücksichtigen, was widersprüchlich und nicht zulässig sei sowie gegen <ref-law> verstosse (Beschwerde, S. 4).
3.2 Nach der bundesgerichtlichen Rechtsprechung sind sowohl die Vorinstanz wie das Bundesgericht selber an den Rückweisungsentscheid gebunden, weshalb bereits entschiedene Fragen nicht mehr zu überprüfen sind, wenn dieselben Fragen erneut unterbreitet werden (<ref-ruling> E. 2.1). Die vom Beschwerdeführer vorgebrachte Rüge richtet sich zwar gegen die straferhöhende Berücksichtigung seiner Vorstrafen, beschlägt jedoch letztlich die Frage, ob das Bundesgericht befugt ist, die Vorinstanz im Rückweisungsentscheid anzuweisen, die von den Parteien nicht gerügte Vernachlässigung der straferhöhenden Wirkung der Vorstrafen des Beschwerdeführers neu zu berücksichtigen. Mit anderen Worten ist vorliegend zu entscheiden, ob das Verschlechterungsverbot (reformatio in peius) eine nachträglich straferhöhende Wirkung der Vorstrafen als unzulässig erscheinen lässt.
Das Bundesgericht führte in seinem Rückweisungsentscheid aus, der in Frage stehende Strafzumessungsfehler führe für sich genommen nicht zur Aufhebung des angefochtenen Urteils, zumal es gemäss <ref-law> nicht über die Begehren der Parteien hinausgehen dürfe (<ref-ruling> E. 6). Das Bundesgericht stellte an gleicher Stelle ebenfalls klar, die Vorinstanz dürfe mit Blick auf das Verschlechterungsverbot insgesamt zwar eine tiefere, aber keine höhere als die bisher ausgesprochene 3 1⁄2-jährige Freiheitsstrafe ausfällen. Eine Verletzung des Verschlechterungsverbots findet demnach nicht statt, wenn einzelne straferhöhende (neben strafmindernden) Faktoren neu berücksichtigt werden, die Strafsanktion insgesamt jedoch nicht erhöht wird. Die Rüge des Beschwerdeführers ist unbegründet.
4. 4.1 Der Beschwerdeführer bringt weiter vor, seine Vorstrafen lägen bereits rund 7 bzw. 5 1⁄2 Jahre zurück, weshalb in Berücksichtigung des Verhältnismässigkeitsprinzips und des Bewährungsgedankens nur noch, wenn überhaupt, eine leichte Straferhöhung in Frage komme. Die von der Vorinstanz vorgenommene "spürbare Straferhöhung" sei nicht verhältnismässig und verstosse gegen den Bewährungsgedanken. Im Ergebnis würden damit <ref-law> und mangels Begründung der Straferhöhung auch <ref-law> verletzt (Beschwerde, S. 7).
Der Beschwerdeführer rügt weiter, die Vorinstanz habe im Urteil vom 18. März 2008 die lange Verfahrensdauer als leicht strafmindernd gewertet, die bis zum angefochtenen Urteil verstrichene Zeit aber nicht zusätzlich strafreduzierend berücksichtigt (Beschwerde, S. 8).
4.2 Die Vorinstanz erwägt, die Vorstrafen lägen bereits lange zurück, es handle sich aber keineswegs um Bagatelldelikte, sondern um gravierende Straftaten gegen das Vermögen. Obwohl diese in Anwendung des Jugendstrafrechts noch nicht zu drastischen Sanktionen gegen den Beschwerdeführer geführt hätten, seien seine einschlägigen Jugendstrafen spürbar straferhöhend zu gewichten (angefochtenes Urteil, S. 9).
Eine deutlich positive Entwicklung des Beschwerdeführers, die strafmindernd zu berücksichtigen wäre, sei nicht erkennbar. Er habe seine Therapie abgebrochen, seit dem Urteil vom 18. März 2008 bereits zwei Mal die Stelle gewechselt und seine Lebensgemeinschaft mit seiner Verlobten vermöge diese ungünstige Entwicklung angesichts des hohen vorbestehenden strukturellen Rückfallrisikos nicht aufzuwiegen, geschweige denn überzukompensieren. Gleiches gelte für den Umstand, dass gegen den Beschwerdeführer seit nunmehr rund vier Jahren keine neuen Strafuntersuchungen wegen Verbrechen oder Vergehen eröffnet worden seien.
4.3 Nach <ref-law> misst das Gericht die Strafe nach dem Verschulden des Täters zu. Es berücksichtigt das Vorleben, die persönlichen Verhältnisse sowie die Wirkung der Strafe auf das Leben des Täters. Es liegt im Ermessen des Sachrichters, in welchem Umfang er die verschiedenen Strafzumessungsfaktoren, worunter auch die Vorstrafen fallen, berücksichtigt. Die Strafrechtliche Abteilung des Bundesgerichts greift auf Beschwerde in Strafsachen hin nur in die Strafzumessung ein, wenn die Vorinstanz den gesetzlichen Strafrahmen über- oder unterschritten hat, wenn sie von rechtlich nicht massgebenden Kriterien ausgegangen ist oder wesentliche Gesichtspunkte ausser Acht gelassen beziehungsweise in Überschreitung oder Missbrauch ihres Ermessens falsch gewichtet hat (<ref-ruling> E. 2.1 mit Hinweisen).
Gemäss <ref-law> ist der Richter gehalten, die Überlegungen, die er bei der Bemessung der Strafe vorgenommen hat, in den Grundzügen wiederzugeben, so dass die Strafzumessung nachvollziehbar ist. Besonders hohe Anforderungen an die Begründung werden unter anderem gestellt, wenn die ausgesprochene Strafe ungewöhnlich hoch oder auffallend milde ist (<ref-ruling> E. 2.1 mit Hinweisen).
4.4 Das angefochtene Urteil verletzt kein Bundesrecht. Die Vorinstanz begründet die spürbare Straferhöhung zu Recht mit dem gravierenden Charakter der einschlägigen Jugendstrafen. Daran ändert nichts, dass diese Delikte bereits lange zurückliegen und seit dem ersten vorinstanzlichen Urteil weitere 15 Monate vergangen sind, in denen keine neuen Strafuntersuchungen gegen den Beschwerdeführer wegen Verbrechen oder Vergehen eröffnet wurden. Diese Umstände zog die Vorinstanz in Erwägung, gewichtete den Deliktscharakter jedoch stärker, was nicht zu beanstanden ist. Weder ist eine Verletzung von <ref-law> noch <ref-law> erkennbar. Die Beschwerde ist in diesem Punkt unbegründet.
5. Die Beschwerde ist abzuweisen, soweit darauf einzutreten ist. Bei diesem Verfahrensausgang sind die bundesgerichtlichen Kosten dem Beschwerdeführer aufzuerlegen (<ref-law>). Der Beschwerdeführer ersucht um Gewährung der unentgeltlichen Rechtspflege. Da das Rechtsmittel von vornherein aussichtslos war, kann dem Gesuch nicht entsprochen werden (<ref-law>). Bei der Festsetzung der Gerichtsgebühr ist seinen finanziellen Verhältnissen Rechnung zu tragen.

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, 23. November 2009
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Favre Keller