Sachverhalt: A. Das Bezirksgericht Zürich verurteilte X._ am 3. September 2009 wegen einfacher Körperverletzung, Sachbeschädigung sowie Gewalt und Drohung gegen Behörden und Beamte zu einer unbedingten Freiheitsstrafe von sechs Monaten, abzüglich 1 Tag Polizeihaft. Das Gericht verpflichtete ihn ausserdem, dem Geschädigten A._ eine Genugtuung von Fr. 500.-- und eine Prozessentschädigung von Fr. 5'081.45 zu entrichten. Es verlängerte zudem die vierjährige Probezeit der mit Strafbefehl der Staatsanwaltschaft Winterthur/Unterland vom 23. März 2005 ausgesprochenen Gefängnisstrafe von drei Monaten um zwei Jahre und die fünfjährige Probezeit der vom Bezirksgericht Zürich am 4. September 2006 ausgefällten Gefängnisstrafe von 13 Monaten um zweieinhalb Jahre. B. Gegen dieses Urteil erklärte X._ Berufung an das Obergericht des Kantons Zürich, das am 4. März 2010 das vorinstanzliche Urteil bestätigte. C. X._ führt Beschwerde in Strafsachen beim Bundesgericht. Er beantragt, die Dispositivziffern 1 alinea 2 (Schuldspruch wegen Sachbeschädigung gemäss Art. 144 StGB), Ziff. 2 und 3 (Strafmass und Vollzug), Ziff. 7 erster Teilsatz (Kostenauflage) sowie Ziff. 9 erster Satz (Kostenauflage im Berufungsverfahren) seien aufzuheben. X._ verlangt ausserdem, dass er lediglich wegen geringfügiger Sachbeschädigung im Sinne von Art. 144 Abs. 1 i.V.m. Art. 172ter StGB schuldig zu sprechen und mit maximal 720 Stunden gemeinnütziger Arbeit zu bestrafen sei. Er beantragt ferner die Gewährung der unentgeltlichen Rechtspflege und Verbeiständung. D. Die Vorinstanz sowie die Oberstaatsanwaltschaft des Kantons Zürich verzichten auf eine Vernehmlassung. 