Sachverhalt: A. A.a Am 5. Juli 2007 erstattete X._ bei der Schaffhauser Polizei Strafanzeige wegen Körperverletzung gegen unbekannte Polizeibeamten. In der Folge wurden zwei Strafverfahren gegen die beiden Polizisten A._ und B._ wegen Verdachts der einfachen Körperverletzung etc. zum Nachteil von X._ eingeleitet. Diese Strafverfahren stellte das Untersuchungsrichteramt des Kantons Schaffhausen am 14. Mai 2008 ein. A.b Gegen den Einstellungsentscheid erhob der Polizist A._ Einsprache bei der Staatsanwaltschaft des Kantons Schaffhausen und beantragte, er sei nicht schuldig zu erklären. Im Einsprache-Entscheid vom 11. Juni 2008 bestätigte die Staatsanwaltschaft die Einstellungsverfügung und stellte zusätzlich die Nichtschuld von A._ fest. A.c Am 8. August 2008 eröffnete das Untersuchungsrichteramt gegen X._ ein Untersuchungsverfahren wegen falscher Anschuldigung und Abgabe eines falschen Zeugnisses zum Nachteil der Polizisten A._ und B._. Mit Strafbefehl vom 29. Dezember 2008 verurteilte das Untersuchungsrichteramt X._ zu einer bedingten Geldstrafe von 150 Tagessätzen zu Fr. 50.--, bei einer Probezeit von vier Jahren, als Zusatzstrafe zum Urteil des Gerichtspräsidiums Laufenburg vom 18. Dezember 2007 wegen SVG-Widerhandlungen. A.d Gegen den Strafbefehl erhob X._ Einsprache. Das Kantonsgericht Schaffhausen bestätigte am 13. Mai 2009 den Schuldspruch sowie die Sanktion gemäss Strafbefehl. B. X._ erklärte Berufung an das Obergericht des Kantons Schaffhausen. Dieses wies die Berufung am 18. Dezember 2009 ab und bestätigte das Urteil des Kantonsgerichts Schaffhausen. C. X._ führt Beschwerde beim Bundesgericht. Er beantragt, der angefochtene Entscheid sei aufzuheben, und er sei freizusprechen bzw. die Sache zur Freisprechung an die Vorinstanz zurückzuweisen. Ihm sei zudem die unentgeltliche Rechtspflege zu gewähren und Rechtsanwalt Roger Gebhard als unentgeltlicher Rechtsvertreter beizugeben. D. Die Staatsanwaltschaft beantragt, die Beschwerde sei abzuweisen. Die Vorinstanz hält an den Erwägungen im angefochtenen Entscheid fest und beantragt sinngemäss die Abweisung der Beschwerde.