Sachverhalt:
A. Am 12. November 2005 kam es zwischen H.C._ (Beschwerdegegner I) und E.A._ (Beschwerdegegner II) zu einer tätlichen Auseinandersetzung, in deren Verlauf letzterer auch ein Messer eingesetzt haben soll.
B. Mit Urteil vom 10. Januar 2007 sprach das Bezirksgericht Zürich H.C._ (Beschwerdegegner I) der einfachen Körperverletzung im Sinne von <ref-law> schuldig und bestrafte ihn mit einer unbedingten Geldstrafe von 190 Tagessätzen zu Fr. 30.-- als Gesamtstrafe. Vom Vorwurf der qualifizierten einfachen Körperverletzung im Sinne von <ref-law> wurde er freigesprochen.
Gleichentags sprach das Bezirksgericht E.A._ (Beschwerdegegner II) der einfachen Körperverletzung im Sinne von Art. 123 Ziff. 1 Abs. 1 und Ziff. 2 Abs. 1 StGB und der Sachbeschädigung im Sinne von <ref-law> schuldig. Vom Vorwurf der mehrfachen Drohung im Sinne von <ref-law> sprach es ihn frei. Er wurde bestraft mit einer bedingten Geldstrafe von 240 Tagessätzen zu Fr. 30.--, wovon 36 Tagessätze als durch Untersuchungshaft geleistet galten.
C. Sowohl H.C._ als auch E.A._ erhoben Berufung. Die Staatsanwaltschaft des Kantons Zürich erhob Anschlussberufung.
D. An der mündlichen Berufungsverhandlung schlossen die Parteien unter Mitwirkung des Obergerichts des Kantons Zürich folgende Vereinbarung:
"1. H.C._ und E.A._ erklären ihr gegenseitiges Desinteresse an der weiteren Strafverfolgung.
2. Jeder Angeklagte verpflichtet sich, die Kosten seines Strafverfahrens (Untersuchungskosten sowie Kosten des erst- und zweitinstanzlichen Gerichtsverfahren), einschliesslich Kosten seiner amtlichen Verteidigung/Rechtsvertretung, zu bezahlen.
3. E.A._ verpflichtet sich, H.C._ als Ausgleich der gegenseitigen Schadenersatz- und Genugtuungsansprüche Fr. 2000.- zu bezahlen, zahlbar in vier monatlichen Raten à Fr. 500.-, erstmals am 1. des Monats, welcher der Rechtskraft der Abschreibungsbeschlüsse folgt."
E. Mit Beschluss vom 21. April 2008 nahm das Obergericht des Kantons Zürich von der Vereinbarung Vormerk und schrieb beide Strafprozesse in Anwendung von <ref-law> als erledigt ab.
F. Mit zwei in den vorliegend wesentlichen Punkten identischen Beschwerden in Strafsachen beantragt die Oberstaatsanwaltschaft des Kantons Zürich die Aufhebung des Beschlusses vom 21. April 2008 und die Rückweisung an die Vorinstanz.
G. Das Obergericht des Kantons Zürich verzichtet auf eine Stellungnahme. Beide Beschwerdegegner beantragen in ihrer Vernehmlassung die Abweisung der Beschwerde. Der Beschwerdegegner I verlangt zudem die unentgeltliche Rechtspflege und Verbeiständung.

Erwägungen:
1. Zur Beschwerde in Strafsachen ist nach <ref-law> berechtigt, wer vor der Vorinstanz am Verfahren teilgenommen hat und ein rechtlich geschütztes Interesse an der Aufhebung oder Änderung des angefochtenen Entscheids hat. Zum Kreis der beschwerdebefugten Parteien zählt namentlich die Staatsanwaltschaft (Art. 81 Abs. 1 lit. b Ziff. 3 BGG).
1.1 Die Beschwerdeführerin hat ein rechtlich geschütztes Interesse an der Aufhebung des angefochtenen Entscheids. Ihr Rechtsschutzinteresse leitet sich aus dem staatlichen Strafanspruch ab, den sie zu vertreten hat (<ref-ruling> E. 1.4.3).
1.2 Der Beschwerdegegner II kritisiert, dass die Staatsanwaltschaft an der obergerichtlichen Berufungsverhandlung nicht teilgenommen habe, obwohl ihr bereits aus dem erstinstanzlichen Verfahren bekannt gewesen sein müsse, dass seitens der Beschwerdegegner eine einvernehmliche Lösung (Rückzug des Strafantrags; Verfahrenseinstellung) angestrebt wurde. Ein solches Versäumnis würde einem Privaten mit Sicherheit als Verwirkung seiner rechtlichen Möglichkeiten angelastet (vgl. Vernehmlassung des Beschwerdegegners II, S. 2).
1.3 Mit der bundesrechtlichen Voraussetzung der Verfahrensteilnahme nach <ref-law> soll verhindert werden, dass sich Parteien, die im kantonalen Verfahren in keiner Form am Prozess mitgewirkt oder daran ein Interesse bekundet haben, erstmals vor Bundesgericht ins Verfahren einschalten können. Dies trifft auf die Oberstaatsanwaltschaft des Kantons Zürich im vorliegenden Fall jedoch nicht zu. Sie hat das Rechtsmittelverfahren zwar nicht selbst geführt, sondern die Anklage von einer ihr untergeordneten Behörde vertreten und damit ihre Interessen mittelbar wahrnehmen lassen (<ref-ruling> E. 1.3.2). Die Staatsanwaltschaft IV des Kantons Zürich hat im Berufungsverfahren Anträge gestellt (vgl. Anschlussberufung vom 16. Mai 2007; act. 12/1) und sich somit in minimaler Form im Sinne von <ref-law> am Verfahren vor Vorinstanz beteiligt. Die Dispensation der Staatsanwaltschaft vom Erscheinen an der mündlichen Berufungsverhandlung (vgl. <ref-law>/ZH) ist von Bundesrechts wegen nicht zu beanstanden. Auf die Beschwerden ist daher einzutreten.
2. Die Beschwerdeführerin macht eine Verletzung von <ref-law> geltend. Zu Unrecht habe die Vorinstanz die Voraussetzungen des bedingten Strafvollzugs (<ref-law>) bejaht und das Interesse der Öffentlichkeit an der Strafverfolgung als gering erachtet.
2.1 <ref-law> (Wiedergutmachung) bestimmt: Hat der Täter den Schaden gedeckt oder alle zumutbaren Anstrengungen unternommen, um das von ihm bewirkte Unrecht auszugleichen, so sieht die zuständige Behörde von einer Strafverfolgung, einer Überweisung an das Gericht oder einer Bestrafung ab, wenn:
a. die Voraussetzungen für die bedingte Freiheitsstrafe (Art. 42) erfüllt sind; und
b. das Interesse der Öffentlichkeit und des Geschädigten an der Strafverfolgung gering sind.
Es stellt sich die Frage, wie der Strafbefreiungsgrund der Wiedergutmachung gemäss <ref-law> im Gerichtsverfahren prozessual zu behandeln ist, ob auch hier eine Einstellung erfolgen kann oder ob bloss eine Strafbefreiung (neben einem Schuldspruch) möglich ist.
2.2 Der Vierte Abschnitt des Dritten Titels (Strafen und Massnahmen) und des Ersten Kapitels (Strafen) des Strafgesetzbuches ist unterteilt in die Strafbefreiung einerseits und die Einstellung des Verfahrens andererseits. Zur Strafbefreiung zählen das fehlende Strafbedürfnis (<ref-law>), die Wiedergutmachung (<ref-law>) und die Betroffenheit des Täters durch seine Tat (<ref-law>). Die Einstellung des Verfahrens (<ref-law>) ist - bei hier nicht zu diskutierenden Voraussetzungen - in allen Verfahrensstadien möglich, wenn ein Ehegatte, eine eingetragene Partnerin, ein eingetragener Partner oder Lebenspartner Opfer ist. Der Gesetzgeber unterscheidet demnach zwischen Strafbefreiung einerseits und Einstellung andererseits. Die in <ref-law> geschaffene Möglichkeit einer Einstellung in allen Verfahrensstadien ist deshalb sinnvoll, weil in Fällen von häuslicher Gewalt die Offizialisierung abgeschwächt und deshalb das Verfahren immer eingestellt werden soll, wenn das Opfer eines Deliktes im sozialen Nahraum die Durchführung eines Strafverfahrens nicht wünscht und ein Eingriff in den partnerschaftlichen Bereich möglichst vermieden werden soll (Christoph Riedo/Nicole Saurer, Basler Kommentar, Strafrecht I, 2. Auflage, Basel 2007, Art. 55 a N 34).
2.3 Der Regelung von <ref-law> liegt der Gedanke zu Grunde, dass selbst bei voller Wiedergutmachung das öffentliche Interesse an einer Strafverfolgung nicht zwingend entfallen muss (vgl. zur amtlichen Publikation vorgesehenes Urteil 6B_346/2008 vom 27. November 2008, E. 3). Unter dem Randnotentitel "1. Gründe für die Strafbefreiung / Wiedergutmachung" bestimmt <ref-law>, dass die zuständige Behörde bei gedecktem Schaden oder hinreichenden Unrechtsausgleichsbemühungen von einer Strafverfolgung, einer Überweisung an das Gericht oder einer Bestrafung absieht. Je nach Verfahrensstadium zeitigt eine Wiedergutmachung somit unterschiedliche Wirkung. Wird das bewirkte Unrecht umgehend ausgeglichen, kann die Untersuchungsbehörde von einer Strafverfolgung absehen. Ist die Strafverfolgung bereits im Gang, so kann die zuständige Behörde (Staatsanwaltschaft) das Verfahren einstellen oder von einer Überweisung an das Gericht absehen. Sind die Voraussetzungen der Wiedergutmachung schliesslich erst im Gerichtsverfahren gegeben, steht dem Gericht als zuständiger Behörde nur noch der Schuldspruch bei gleichzeitigem Strafverzicht offen (Franz Riklin, Basler Kommentar - Strafrecht I, 2. Auflage, Basel 2007, Vor Art. 52 f. N 18 und 24-29; Felix Bommer, Bemerkungen zur Wiedergutmachung, forumpoenale 3/2008, S.175 - 177; Silvan Flückiger, <ref-law>/Art. 54 f. StGBneu - Betroffenheit durch Tatfolgen, Straftatfolgen als Einstellungsgrund und Strafersatz? Bern 2006, S. 79; a.M. Christian Schwarzenegger/Markus Hug/Daniel Jositsch, Strafrecht II, 8. Auflage, Zürich 2007, S. 68; Daniel Jositsch, Strafbefreiung gemäss Art. 52 f. StGBneu und prozessrechtliche Umsetzung, SJZ 100/2004, S. 9).
Die unterschiedlichen Rechtsfolgen in den verschieden Verfahrensstadien sind vom Gesetzgeber gewollt. Nur bei ganz offensichtlichen Fällen soll bereits den Untersuchungsbehörden die Möglichkeit gegeben werden, ein Verfahren gar nicht an die Hand zu nehmen und gegebenenfalls einzustellen, um ein langes und aufwändiges Verfahren zu vermeiden, das einerseits für die Betroffenen eine Belastung darstellen kann und andererseits dem Grundsatz der Prozessökonomie zuwiderlaufen würde. Im Gerichtsverfahren andererseits wäre eine reine Wiedergutmachung ohne jede strafrechtliche Komponente der Strafe unterlegen. Die wesentlichen Abschreckungselemente des Strafrechts bleiben nur erhalten, wenn man die Strafdrohung, die staatliche Strafverfolgung, das Strafverfahren und den strafrechtlichen Schuldspruch neben der Wiedergutmachung beibehält (vgl. Heinz Schöch, Empfehlen sich Anmerkungen oder Ergänzungen bei den strafrechtlichen Sanktionen, ohne Freiheitsentzug, Gutachten C am 59. deutschen Juristentag, München 1992 zum Allgemeinen Entwurf zur Wiedergutmachung C 64). Mit dieser Differenzierung schuf der Gesetzgeber die Möglichkeit, dem Einzelfall gerecht zu werden und dem Grundsatz besser zu genügen, Gleiches gleich und Ungleiches ungleich zu behandeln (Obergericht des Kantons Zürich, I. Strafkammer, Urteil vom 12. September 1996 zu Art. 66bis aStGB, ZR 1997, Nr. 59, S. 153, vom Bundesgericht bestätigt: Entscheid 6S.4/1997 vom 4. Februar 1997).
2.4 Zusammenfassend ist demnach festzuhalten, dass die Vorinstanz <ref-law> verletzt hat, als sie von der Vereinbarung zwischen den Beschwerdegegnern bloss Vormerk nahm und den Strafprozess als erledigt abschrieb. Eine Einstellung aufgrund Wiedergutmachung ist nach dem Ausgeführten im Gerichtsverfahren von Bundesrechts wegen ausgeschlossen. Abweichendes kantonales Strafprozessrecht ist insoweit unbeachtlich (<ref-law>). Bei der erneuten Befassung wird die Vorinstanz bei gegebenen Tatbestandsvoraussetzungen einen Schuldspruch auszufällen haben. Dabei wird sie sich in Bezug auf die Vorwürfe gegen den Beschwerdegegner I vorab auch mit der Frage des Strafantragsrückzugs auseinandersetzen müssen. Sofern die von der Beschwerdeführerin vorliegend bestrittenen Voraussetzungen der Wiedergutmachung nach <ref-law> (bedingter Strafvollzug; öffentliches Interesse an der Strafverfolgung) gegeben sind, wird sie von einer Bestrafung abzusehen haben.
3. Bei diesem Ausgang sind die Kosten grundsätzlich den unterliegenden Beschwerdegegnern aufzuerlegen (<ref-law>). Der Beschwerdegegner I ersucht jedoch um unentgeltliche Rechtspflege. Seine Bedürftigkeit ist ausgewiesen und sein Gesuch, in welchem er sich mit eingehender Begründung den Ausführungen und dem Beschluss des Obergerichts anschliesst, war nicht aussichtslos. Die unentgeltliche Rechtspflege und Verbeiständung ist ihm demnach zu gewähren (Art. 64 Abs. 1 und 2 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen, der Beschluss des Obergerichts des Kantons Zürich vom 21. April 2008 aufgehoben und die Angelegenheit zu neuer Entscheidung an die Vorinstanz zurückgewiesen.
2. Das Gesuch um unentgeltliche Rechtspflege des Beschwerdegegners I wird gutgeheissen. Es werden ihm keine Kosten auferlegt. Seinem Vertreter, Rechtsanwalt lic. iur. Christian Koch, wird eine Entschädigung von Fr. 2'000.-- aus der Bundesgerichtskasse ausgerichtet.
3. Dem Beschwerdegegner II werden Gerichtskosten von Fr. 2'000.-- auferlegt.
4. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, I. Strafkammer, schriftlich mitgeteilt.
Lausanne, 27. November 2008
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Schneider Thommen