Der Einzelrichter zieht in Erwägung:
1.
Am 19. Juli 2009 alarmierte Y._ die Polizei, nachdem es zwischen ihr und ihrem Partner X._ zu einer tätlichen Auseinandersetzung gekommen war. Infolge widersprüchlicher Angaben konnte die Polizei den genauen Tathergang nicht ermitteln und erfasste in der Strafanzeige beide Beteiligten sowohl als Täter wie auch als Opfer von häuslicher Gewalt.
Y._ zufolge soll X._ sie bei ihrer Rückkehr in die gemeinsame Wohnung beschimpft und tätlich angegangen haben. Sie habe sich zu wehren versucht, und als er sie gewürgt habe, habe sie ihn in die Hand gebissen. Schliesslich habe sie ins Schlafzimmer flüchten können und von dort aus die Polizei angerufen.
Gemäss den Schilderungen von X._ habe Y._ ihn für Sexspiele ans Bett fesseln wollen. Weil er keine Lust gehabt habe, sei sie wütend geworden und habe einen Holzklotz vom Balkon geholt. Mit diesem habe sie ihm mehrmals auf den Fuss geschlagen, so dass er sich zwei Zehen gebrochen habe.
2.
Während die Staatsanwaltschaft Basel-Stadt gegen X._ Anklage erhob, stellte sie das Strafverfahren gegen Y._ am 18. September 2012 ein. Zur Begründung führte sie aus, die Aussagen der Beteiligten widersprächen sich diametral, und es gebe weder Zeugen noch objektive Beweismittel, die der Wahrheitsfindung dienen könnten. Deshalb lasse sich kein Tatverdacht gegen Y._ erhärten, der eine Anklage rechtfertigte.
Die gegen diese Einstellungsverfügung erhobene Beschwerde von X._ wies das Appellationsgericht des Kantons Basel-Stadt am 3. Juli 2013 ab.
3.
Mit Beschwerde in Strafsachen beantragt X._, der vorinstanzliche Entscheid sei aufzuheben und die Sache zur Anklageerhebung gegen Y._ wegen einfacher Körperverletzung zu seinem Nachteil an die Staatsanwaltschaft Basel-Stadt zurückzuweisen. Eventualiter sei die Angelegenheit zur neuen Entscheidung an die Vorinstanz zurückzuweisen. X._ ersucht um unentgeltliche Rechtspflege.
Die Staatsanwaltschaft Basel-Stadt und das Appellationsgericht des Kantons Basel-Stadt verzichten auf eine Vernehmlassung. Y._ beantragt die Abweisung der Beschwerde. Sie ersucht um unentgeltliche Rechtspflege.
4.
4.1. Nach <ref-law> ist zur Beschwerde in Strafsachen berechtigt, wer vor der Vorinstanz am Verfahren teilgenommen oder keine Möglichkeit zur Teilnahme erhalten hat (lit. a), sofern er ein aktuelles rechtlich geschütztes Interesse an der Aufhebung oder Änderung des angefochtenen Entscheids hat (lit. b). Der Privatklägerschaft wird ein rechtlich geschütztes Interesse zuerkannt, wenn der angefochtene Entscheid sich auf die Beurteilung ihrer Zivilansprüche auswirken kann (Art. 81 Abs. 1 lit. b Ziff. 5 BGG). Dies setzt grundsätzlich voraus, dass der Privatkläger bereits adhäsionsweise Zivilforderungen geltend gemacht hat. Bei Nichtanhandnahme oder Einstellung der Strafuntersuchung wird auf dieses Erfordernis verzichtet. In diesen Fällen muss im Verfahren vor Bundesgericht aber dargelegt werden, aus welchen Gründen sich der angefochtene Entscheid inwiefern auf welche Zivilforderungen auswirken kann (<ref-ruling> E. 1.3.1 mit Hinweisen).
4.2. Der Beschwerdeführer hat im vorinstanzlichen Verfahren keine Zivilansprüche geltend gemacht. Er legt auch in seiner Beschwerde an das Bundesgericht nicht dar, aus welchen Gründen sich der angefochtene Entscheid inwiefern auf welche Zivilforderungen auswirken kann. Es fehlt ihm die Beschwerdelegitimation nach Art. 81 Abs. 1 lit. b Ziff. 5 BGG. Ebenso wenig ist er nach der "Star-Praxis" zur Beschwerde legitimiert, da er keine Verletzung von Verfahrensrechten rügt (vgl. <ref-ruling> E. 1.4.; <ref-ruling> E. 3.2; je mit Hinweisen).
5.
Auf die Beschwerde ist im Verfahren nach <ref-law> nicht einzutreten. Bei diesem Ausgang sind die bundesgerichtlichen Kosten dem Beschwerdeführer aufzuerlegen (<ref-law>). Sein Gesuch um Gewährung der unentgeltlichen Rechtspflege ist abzuweisen, da die Beschwerde von vornherein aussichtslos erschien. Seiner finanziellen Lage ist mit herabgesetzten Gerichtskosten Rechnung zu tragen (<ref-law>).
Der Beschwerdeführer hat der anwaltlich vertretenen Beschwerdegegnerin 2 eine angemessene Parteientschädigung zu bezahlen (<ref-law>). Diese ist praxisgemäss ihrer Rechtsvertreterin auszurichten. Ihr Gesuch um unentgeltliche Rechtspflege wird gegenstandslos.

Demnach erkennt der Einzelrichter:
1.
Auf die Beschwerde wird nicht eingetreten.
2.
Das Gesuch des Beschwerdeführers um unentgeltliche Rechtspflege wird abgewiesen.
3.
Das Gesuch der Beschwerdegegnerin 2 um unentgeltliche Rechtspflege wird als gegenstandslos abgeschrieben.
4.
Die Gerichtskosten von Fr. 800.-- werden dem Beschwerdeführer auferlegt.
5.
Der Beschwerdeführer hat der Rechtsvertreterin der Beschwerdegegnerin 2, Advokatin Evelyne Alder, eine Parteientschädigung von Fr. 1'500.-- zu entrichten.
6.
Dieses Urteil wird den Parteien und dem Appellationsgericht des Kantons Basel-Stadt, Appellationsgerichtspräsidentin, schriftlich mitgeteilt.
Lausanne, 24. Januar 2014
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Einzelrichter: Oberholzer
Die Gerichtsschreiberin: Siegenthaler