Sachverhalt: A. Mit Zahlungsbefehl vom 3. November 2010 hatte X._ gegen Z._ für Fr. 94'688.-- nebst Zins zu 5 % seit 1. Januar 2010 die Betreibung eingeleitet (Betreibung Nr. ... des Betreibungsamts Basel-Stadt). B. Nachdem der Betriebene Rechtsvorschlag erhoben hatte, ersuchte X._ am 15. November 2010 das Zivilgericht Basel-Stadt um provisorische Rechtsöffnung. Hierfür stützte er sich auf eine Kopie eines handschriftlichen Dokumentes mit dem Titel "Schuldschein-Bestätigung". Mit Entscheid vom 1. März 2011 wies das Zivilgericht Basel-Stadt das Rechtsöffnungsgesuch ab. Die hierauf erhobene Beschwerde wies das Appellationsgericht des Kantons Basel-Stadt mit Entscheid vom 2. März 2012 ab. C. Mit Beschwerde vom 16. Mai 2012 (Datum der Postaufgabe) gelangt X._ (fortan Beschwerdeführer) an das Bundesgericht. Er beantragt, das Urteil des Appellationsgerichts aufzuheben, und verlangt "Zurückweisung an die Vorinstanzen zur neuen Beurteilung oder Sistierung wegen Strafanzeige und laufenden Ermittlungen". Da willkürlich gehandelt worden sei, müsse eine Strafuntersuchung stattfinden. Weiter ersucht der Beschwerdeführer um eine "Wiedergutmachungs-Summe nach richterlichem Ermessen" sowie um unentgeltliche Rechtspflege. Das Bundesgericht hat die kantonalen Akten, aber keine Vernehmlassungen eingeholt.