Sachverhalt:
A. Das Obergericht des Kantons Zürich verurteilte X._ mit Urteil vom 11. Oktober 2007 in zweiter Instanz zu einer teilbedingten Freiheitsstrafe von 30 Monaten. Den unbedingt zu vollziehenden Teil der Freiheitsstrafe setzte es auf 15 Monate fest, abzüglich 39 Tage Untersuchungshaft. Daraufhin versetzte der Justizvollzug des Kantons Zürich X._ mit Vollzugsauftrag vom 31. Dezember 2007 rückwirkend per 11. Oktober 2007 in den ordentlichen Strafvollzug.
B. X._ wurde in anderer Angelegenheit am 25. Juli 2007 in Untersuchungshaft genommen und mit Urteil des Bezirksgerichts Zürich vom 19. Juni 2008 zu 4 Jahren Freiheitsstrafe verurteilt, als Zusatzstrafe unter anderem zum Urteil des Obergerichts des Kantons Zürich vom 11. Oktober 2007. Dagegen erklärte X._ die Berufung. Das Obergericht des Kantons Zürich sprach ihn mit Urteil vom 7. April 2009 vom Vorwurf der mehrfachen Vergewaltigung frei. In Ziffer 5 des Urteilsdispositivs erkannte es ihm eine Genugtuung von Fr. 25'000.-- zu.
C. Mit Beschwerde in Strafsachen bzw. mit Beschwerde in öffentlich-rechtlichen Angelegenheiten beantragt X._, Ziffer 5 des Urteils des Obergerichts des Kantons Zürich vom 7. April 2009 sei aufzuheben. Die Untersuchungshaft von 78 Tagen und der vorzeitige Strafvollzug von 293 Tagen seien auf die mit Urteil des Obergerichts des Kantons Zürich vom 11. Oktober 2007 zu vollziehende Freiheitsstrafe von 15 Monaten anzurechnen. Er sei mit sofortiger Wirkung aus dem ordentlichen Strafvollzug zu entlassen und ihm sei für die Überhaft eine Genugtuung von mindestens Fr. 30'000.-- aus der Staatskasse zu bezahlen. Zudem ersucht X._ um unentgeltliche Prozessführung und Verbeiständung.
D. Die Oberstaatsanwaltschaft des Kantons Zürich und das Obergericht des Kantons Zürich verzichten beide auf Vernehmlassung.

Erwägungen:
1. Der Beschwerdeführer macht eine Verletzung von <ref-law> durch Nichtanrechnung der Untersuchungshaft geltend.
1.1 Gemäss <ref-law> rechnet das Gericht die Untersuchungshaft, die der Täter während dieses oder eines anderen Verfahrens ausgestanden hat, auf die Strafe an. Nach <ref-law> ist Untersuchungshaft jede in einem Strafverfahren verhängte Haft, Untersuchungs-, Sicherheits- und Auslieferungshaft. Ohne jede Einschränkung anzurechnen ist auch der vorzeitig angetretene Strafvollzug (<ref-law>).
1.2 Die Vorinstanz führt aus, eine Rechtsgrundlage für die Anrechnung der Haft auf die Vorstrafe vom 11. Oktober 2007 sei nicht ersichtlich. Im vorliegenden Verfahren sei keine Bestrafung, sondern ein vollumfänglicher Freispruch des Beschwerdeführers erfolgt, weshalb <ref-law> nicht anwendbar sei. Hingegen sei der Beschwerdeführer für die Haft in Geld zu entschädigen. Er habe sich ab dem 11. Oktober 2007 im ordentlichen Vollzug seiner Vorstrafe befunden. Deshalb sei die von ihm von diesem Zeitpunkt an bis am 18. Juni 2008 erstandene Haft auf die noch zu verbüssende Reststrafe aus der Verurteilung vom 11. Oktober 2007 anzurechnen. Am 19. Juni 2008 sei der Beschwerdeführer in den vorzeitigen Strafvollzug betreffend das vorliegende Verfahren versetzt worden. Der Beschwerdeführer habe demnach vom 25. Juli 2007 bis am 10. Oktober 2007 und vom 19. Juni 2008 bis zum Urteilszeitpunkt - insgesamt 371 Tage - unschuldig im Freiheitsentzug verbracht. Dafür sei ihm eine Genugtuung von Fr. 25'000.-- zuzusprechen (angefochtenes Urteil E. IV. S. 17 ff.).
1.3 Der Beschwerdeführer bringt vor, die Vorinstanz habe anstelle der Anrechnung der Untersuchungshaft und des vorzeitigen Strafvollzugs auf den in einem anderen Verfahren noch ausstehenden Strafvollzug von 15 Monaten eine Haftentschädigung ausgerichtet. Gemäss Urteil des Obergerichts des Kantons Zürich vom 11. Oktober 2007 habe er 39 Tage in Untersuchungshaft verbracht. 252 Tage (vom 11. Oktober 2007 bis am 18. Juni 2008) habe er als ordentlichen Strafvollzug verbüsst. Weiter seien ihm 78 Tage Untersuchungshaft sowie 293 Tage vorzeitiger Strafvollzug aus dem vorliegenden Strafverfahren anzurechnen. Somit habe er bis zum 7. April 2009 insgesamt bereits 662 Tage verbüsst, was eine Überhaft von 212 Tagen ergebe. Deshalb sei er mit sofortiger Wirkung aus dem Strafvollzug zu entlassen und für die Überhaft angemessen zu entschädigen.
1.4 Nach der bundesgerichtlichen Rechtsprechung verletzt die Ausrichtung einer Haftentschädigung anstelle der Anrechnung der Überhaft auf den in einem anderen Verfahren angeordneten Vollzug Bundesrecht. Im Bereich der Haftanrechnung haben weder der Grundsatz der Tat- noch jener der Verfahrensidentität länger Geltung. Es gilt der Grundsatz, dass zu entziehende Freiheit wenn immer möglich mit bereits entzogener Freiheit zu kompensieren ist (BGE 6B_1023/2008 vom 7. Mai 2009 E. 1.3.6; <ref-ruling> E. 5.1 S. 155 f. mit Hinweisen).
1.5 Die Vorinstanz verweist für ihre Begründung, wonach die Anrechnung der Haft nur bei einer Verurteilung erfolge, auf die Literatur. Sie folgert, bei einem Freispruch sei deshalb <ref-law> nicht anwendbar (s. angefochtenes Urteil E. IV. E. 2.2 S. 18 mit Hinweis auf CHRISTOPH METTLER, in: Basler Kommentar, Strafrecht I, 2. Aufl. 2007, N. 3 Art. 51). Damit verkennt die Vorinstanz die bundesrechtliche Rechtsprechung, wonach der Grundsatz der Tatidentität nicht mehr gilt. Für die Anrechnung ist lediglich erforderlich, dass eines von mehreren Strafverfahren zu einer Verurteilung führt. Im Gegensatz zur früheren Rechtsprechung ist unerheblich, dass die Untersuchungshaft bzw. der vorzeitige Strafvollzug anlässlich des vorliegenden Verfahrens erfolgte, welches zu einem Freispruch geführt hat (vgl. METTLER, a.a.O., N. 38). Die Rüge der Verletzung von <ref-law> erweist sich demnach als begründet. Ziffer 5 des angefochtenen Urteils ist aufzuheben und die Sache zur neuen Entscheidung an die Vorinstanz zurückzuweisen (<ref-law>). Diese wird die nach Anrechnung der Untersuchungshaft bzw. des vorzeitigen Strafvollzugs verbleibende Überhaft neu zu berechnen sowie die daraus resultierende Genugtuung neu zu bemessen haben.
1.6 Nach dem Gesagten ist auf den Antrag auf Erhöhung der Genugtuung, welcher der Beschwerdeführer zu Recht im Rahmen der Beschwerde in öffentlich-rechtlichen Angelegenheiten erhoben hat, nicht einzugehen. Auf den Antrag auf sofortige Entlassung aus dem ordentlichen Strafvollzug ist mangels Zuständigkeit nicht einzutreten.
2. Die Beschwerde ist gutzuheissen, womit das Gesuch um unentgeltliche Rechtspflege und Verbeiständung gegenstandslos wird. Es sind keine Gerichtskosten zu erheben (<ref-law>). Der Kanton Zürich hat dem Beschwerdeführer dessen Parteikosten zu ersetzen (<ref-law>). Die Entschädigung ist dem Vertreter des Beschwerdeführers zuzusprechen.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen, Ziffer 5 des Urteils des Obergerichts des Kantons Zürich vom 7. April 2009 aufgehoben und die Sache zu neuer Entscheidung an die Vorinstanz zurückgewiesen.
2. Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird als gegenstandslos abgeschrieben.
3. Es werden keine Gerichtskosten erhoben.
4. Der Kanton Zürich hat dem Vertreter des Beschwerdeführers, Rechtsanwalt Alexander Prechtl eine Parteientschädigung von Fr. 3'000.-- auszurichten.
5. Dieses Urteil wird den Parteien, dem Obergericht des Kantons Zürich, II. Strafkammer, sowie dem Amt für Justizvollzug des Kantons Zürich schriftlich mitgeteilt.
Lausanne, 16. Juni 2009
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Das präsidierende Mitglied: Die Gerichtsschreiberin:
Schneider Binz