Sachverhalt:
A.
A.a. Am 11. Juni 2020 belegte das zuständige Gericht auf Antrag der B._, (Verfahrensbeteiligte), die künftigen Lohnforderungen von C.A._ gestützt auf <ref-law> für die Dauer eines Jahres mit Arrest. Die von A.A._ (Beschwerdeführer) gegen den Arrestbefehl erhobene Einsprache wies das Zivilgericht des Kantons Basel-Stadt mit Entscheid vom 17. März 2021 ab.
A.b. Gegen diesen Entscheid reichte A.A._ Beschwerde beim Appellationsgericht Basel-Stadt ein, wobei er für das Beschwerdeverfahren um unentgeltliche Rechtspflege und Verbeiständung ersuchte.
B.
Mit Verfügung vom 20. Mai 2021 (eröffnet am 26. Mai 2021) wies der Präsident des Appellationsgerichts das Gesuch um unentgeltliche Rechtspflege für das Beschwerdeverfahren ab und forderte A.A._ zur Bezahlung eines Kostenvorschusses auf.
C.
A.A._ gelangt mit subsidiärer Verfassungsbeschwerde vom 23. Juni 2021 mit dem Antrag ans Bundesgericht, es sei die Verfügung vom 20. Mai 2021 aufzuheben und ihm für das Beschwerdeverfahren vor dem Appellationsgericht die unentgeltliche Rechtspflege und Verbeiständung zu gewähren. Eventuell sei die Sache zur Neubeurteilung an das Appellationsgericht zurückzuweisen. Ausserdem ersucht A.A._ auch für das bundesgerichtliche Verfahren um unentgeltliche Rechtspflege und Beiordnung seines Rechtsanwalts als unentgeltlichen Vertreter.
Mit Vernehmlassung vom 28. Juni 2021 schliesst der Präsident des Appellationsgerichts auf Abweisung der Beschwerde, woraufhin A.A._ mit Stellungnahme vom 15. Juli 2021 an seinen bisherigen Anträgen festhält. Am 28. September 2021 beantragt die B._, es sei auf die Beschwerde nicht einzutreten, eventualiter sei diese abzuweisen.
Im Übrigen hat das Bundesgericht die Akten des kantonalen Verfahrens eingeholt.

Erwägungen:
1.
1.1. Angefochten ist der (kantonal letztinstanzliche; <ref-law>) Entscheid über die unentgeltliche Rechtspflege in einem Beschwerdeverfahren bezüglich eine Arresteinsprache. Da der Entscheid im Rahmen eines Rechtsmittelverfahrens getroffen wurde, bleibt unerheblich, dass die Vorinstanz als einzige kantonale Instanz entschieden hat (vgl. <ref-law>; <ref-ruling> E. 1.2; <ref-ruling> E. 1.1). Entscheide über die unentgeltliche Rechtspflege sind Zwischenentscheide nach <ref-law>, die praxisgemäss in der Regel einen nicht wieder gutzumachenden Nachteil bewirken können (Art. 93 Abs. 1 Bst. a BGG; vgl. statt vieler Urteil 5A_508/2020 vom 6. Oktober 2020 E. 1.1; betreffend ein Arrestverfahren vgl. Urteil 5A_145/2008 vom 11. April 2008 E. 1). Dem Beschwerdeführer droht ein derartiger Nachteil jedenfalls deshalb, weil ihm mit der Abweisung seines Gesuchs um unentgeltliche Rechtspflege Frist zur Leistung eines Kostenvorschusses angesetzt wurde. Folglich besteht die Gefahr, dass bei Nichtbezahlen des Vorschusses auf die Hauptsache nicht eingetreten wird (vorne Bst. B; Urteile 5A_536/2020 vom 23. November 2020 E. 4.1; 5A_988/2019 vom 3. Juni 2020 E. 3.1). Unter diesen Umständen bleibt unerheblich, dass der Beschwerdeführer sich zu dieser Problematik nicht äussert.
Bei Zwischenentscheiden folgt der Rechtsweg jenem der Hauptsache (<ref-ruling> E. 1.1). Dort steht eine Schuldbetreibungs- und Konkurssache in Streit, die nach Art. 72 Abs. 2 Bst. a BGG der Beschwerde in Zivilsachen unterliegt (Urteile 5A_248/2020 vom 30. Juni 2021 E. 1.1; 5A_821/2018 vom 17. Oktober 2018 E. 2). Der Beschwerdeführer gibt den Streitwert in dieser vermögensrechtlichen Angelegenheit mit Fr. 28'512.-- an (vgl. Art. 74 Abs. 1 und Art. 51 Abs. 1 Bst. c BGG). Wie es sich mit der Höhe des Streitwerts im Einzelnen verhält (vgl. <ref-ruling> E. 4.3; Urteil 5A_370/2018 vom 27. März 2019 E. 1) braucht freilich nicht geklärt zu werden: Entscheide über Arresteinsprachen sind Entscheide über vorsorgliche Massnahmen (<ref-ruling> E. 1.2; Urteil 5A_593/2020 vom 17. Februar 2021 E. 2). Unbesehen darum, ob die Beschwerde in Zivilsachen oder die subsidiäre Verfassungsbeschwerde das zutreffende Rechtsmittel ist, kann damit auch im vorliegenden Verfahren nur die Verletzung von verfassungsmässigen Rechten geltend gemacht werden (Art. 98 und 116 BGG; vgl. sogleich E. 1.2).
Der Beschwerdeführer ist nach Art. 76 Abs. 1 bzw. <ref-law> zur Beschwerde berechtigt, die er auch fristgerecht eingereicht hat (Art. 100 Abs. 1 und Art. 117 BGG). Auf die Beschwerde ist einzutreten.
1.2. Im Hauptsacheverfahren (Arresteinsprache) kann nur die Verletzung verfassungsmässiger Rechte gerügt werden (vgl. E. 1.1 hiervor), was auch hinsichtlich der tatsächlichen Feststellungen der Vorinstanz gilt (<ref-ruling> E. 4.1). Damit kann der Beschwerdeführer auch im Streit um das für das diesbezügliche Verfahren beantragte Recht auf unentgeltliche Rechtspflege nur die Verletzung derartiger Rechte geltend machen (Urteile 5A_1012/2020 vom 3. Mai 2021 E. 2; 5A_455/2020 vom 1. September 2020 E. 3). Die Rüge der Verletzung verfassungsmässiger Rechte muss gemäss dem strengen Rügeprinzip von <ref-law> in der Beschwerde vorgebracht und begründet werden. Die rechtsuchende Partei muss dabei präzise angeben, welches verfassungsmässige Recht durch den angefochtenen Entscheid verletzt wurde, und im Einzelnen darlegen, worin die Verletzung besteht. Das Bundesgericht prüft nur klar und detailliert erhobene und soweit möglich belegte Rügen. Auf ungenügend begründete Rügen und rein appellatorische Kritik am angefochtenen Entscheid tritt es nicht ein (<ref-ruling> E. 1.3; <ref-ruling> E. 2.3).
2.
2.1. Die Vorinstanz hat das Gesuch des Beschwerdeführers um unentgeltliche Rechtspflege abgewiesen, weil dieser über ein monatliches Einkommen von insgesamt Fr. 6'706.-- verfüge und daher nicht bedürftig sei. Der Beschwerdeführer beziffert sein Einkommen dagegen mit monatlich Fr. 1'556.--. Damit könne er seinen (unbestrittenen) Bedarf von Fr. 2'391.-- im Monat nicht decken und sei bedürftig.
Nach <ref-law> hat jede Person, die nicht über die erforderlichen Mittel verfügt, Anspruch auf unentgeltliche Rechtspflege, wenn ihr Rechtsbegehren nicht aussichtslos erscheint. Soweit es zur Wahrung ihrer Rechte notwendig ist, hat sie ausserdem Anspruch auf unentgeltlichen Rechtsbeistand. Hierbei handelt es sich um eine verfassungsrechtliche Minimalgarantie, deren Einhaltung das Bundesgericht bei genügender Rüge trotz seiner grundsätzlich beschränkten Kognition (vgl. vorne E. 1.2) in rechtlicher Hinsicht frei prüft (<ref-ruling> E. 4.1). Bezüglich der tatsächlichen Feststellungen der Vorinstanz kann vor Bundesgericht dagegen nur die Verletzung verfassungsmässiger Rechte geltend gemacht werden, namentlich des Willkürverbots (<ref-law>; <ref-ruling> E. 5.1; Urteil 5D_125/2018 vom 24. Oktober 2018 E. 2).
2.2. Eine Person ist bedürftig, wenn sie nicht in der Lage ist, für die Prozesskosten aufzukommen, ohne dass sie Mittel beanspruchen muss, die zur Deckung des Grundbedarfs für sie und ihre Familie notwendig sind. Bei der Prüfung der Mittellosigkeit hat die entscheidende Behörde der gesamten wirtschaftlichen Situation der gesuchstellenden Person im Zeitpunkt der Einreichung des Gesuchs Rechnung zu tragen (<ref-ruling> E. 4.1; <ref-ruling> E. 5.1). Dabei obliegt es der um unentgeltliche Rechtspflege ersuchenden Person, sowohl ihre Einkommens- und Vermögensverhältnisse als auch alle ihre finanziellen Verpflichtungen umfassend darzustellen und soweit möglich zu belegen. An eine umfassende und klare Darstellung der finanziellen Situation dürfen umso höhere Anforderungen gestellt werden, je komplexer die finanziellen Verhältnisse sind. Die gesuchstellende Person trifft eine umfassende Mitwirkungspflicht. Bei einer anwaltlich vertretenen Gesuchstellerin ist das Gericht sodann nicht verpflichtet, eine Nachfrist anzusetzen, damit ein unvollständiges oder unklares Gesuch verbessert werden kann. Wenn die anwaltlich vertretene Person ihren Obliegenheiten nicht genügend nachkommt, kann das Gesuch mangels ausreichender Substanziierung oder mangels Bedürftigkeitsnachweises abgewiesen werden (<ref-ruling> E. 4a; <ref-ruling> E. 3a; Urteile 2C_367/2020 vom 7. Oktober 2020 E. 3.3; 5A_716/2018 vom 27. November 2018 E. 3.2).
3.
3.1. Unbestritten erzielt der Beschwerdeführer aufgrund einer Anstellung bei der D._ AG ein monatliches Nettoeinkommen von gerundet Fr. 1'556.--. Die Vorinstanz erachtet es allerdings nicht als glaubhaft, dass dies sein einziges Erwerbseinkommen ist. Aus dem bei den Akten liegenden Lohnausweis für das Jahr 2020 ergebe sich vielmehr, dass der Beschwerdeführer auch bei der E._ AG arbeite und dort ein Einkommen von monatlich netto Fr. 2'733.-- erwirtschafte. Es sei weder behauptet noch glaubhaft gemacht, dass dieses Anstellungsverhältnis zwischenzeitlich aufgelöst worden sei. Gemäss der Trennungsvereinbarung vom 24. Mai 2020 habe der Beschwerdeführer sodann gegenüber seiner Ehefrau Anspruch auf monatliche Unterhaltsbeiträge über Fr. 2'417.--. Dass diese Beiträge uneinbringlich seien, sei nicht glaubhaft. Das Gesamteinkommen von Fr. 6'706.-- im Monat erlaube dem Beschwerdeführer bei einem Bedarf von monatlich Fr. 2'391.-- die Tragung seiner Prozesskosten. Für diese Kosten könne der Beschwerdeführer im Übrigen selbst dann aufkommen, wenn er neben dem bei der D._ AG erzielten Einkommen nur entweder über ein weiteres Erwerbseinkommen oder die Unterhaltsbeiträge verfüge.
3.2. Im Zusammenhang mit dem Einkommen bei der E._ AG erachtet der Beschwerdeführer den angefochtenen Entscheid als willkürlich. 2021 habe das entsprechende Arbeitsverhältnis nicht mehr bestanden und habe er, der Beschwerdeführer, dieses Einkommen nicht mehr erzielt, ansonsten er dies in seinem Gesuch angegeben und er die entsprechenden Lohnabrechnungen eingereicht hätte. Auch den aktenkundigen Kontounterlagen lasse sich entnehmen, dass im Jahr 2021 keine Zahlungen der früheren Arbeitgeberin mehr erfolgt seien. Sämtliche Unterlagen hätten dem Gesuch beigelegen und seien der Vorinstanz bekannt gewesen. Der Beschwerdeführer habe mit seinen Angaben zur früheren Anstellung nur dem Gesuchsformular nachgelebt, welches verlange, dass dem Gesuch der Lohnausweis des Vorjahres und die letzten Lohnabrechnungen beigelegt würden. Unter diesen Umständen sei offenkundig, dass das Arbeitsverhältnis mit der E._ AG nicht mehr bestehe und dürfe das entsprechende Einkommen nicht mehr angerechnet werden. Mit ihren Ausführungen unterstelle die Vorinstanz dem Beschwerdeführer, er habe falsche Angaben zu seinem Einkommen gemacht und Belege zurückgehalten. Dies sei unzulässig und entbehre jeglicher Grundlage.
3.3. Es obliegt der um unentgeltliche Rechtspflege ersuchenden Person, ihre finanziellen Verhältnisse umfassend und klar anzugeben (vgl. vorne E. 2.2). Dabei ist sie unter Umständen auch gehalten, sich dazu zu äussern, wie sie kurz vor Gesuchseinreichung noch vorhandene, zwischenzeitlich aber weggefallene Vermögenswerte verwendet hat (Urteil 5P.310/2003 vom 23. Oktober 2003 E. 3.5; BÜHLER, in: Berner Kommentar, Schweizerische Zivilprozessordnung, Band I, 2012, N. 90 zu <ref-law> [zum Verhältnis zwischen den <ref-law> und <ref-law> vgl. <ref-ruling> E. 4.1; <ref-ruling> E. 4.1]). Vor diesem Hintergrund konnte die Vorinstanz vom Beschwerdeführer ohne Verfassungsverletzung eine Erklärung zum angeblich unmittelbar vor dem massgeblichen Zeitpunkt entfallenen Einkommen bei der E._ AG sowie die Beibringung entsprechender Unterlagen erwarten. Dies muss umso mehr gelten, als der Beschwerdeführer anwaltlich vertreten war und die Unsicherheiten zu seinem Einkommen aufgrund seiner eigenen Angaben bzw. den von ihm eingereichten Belegen entstanden. Unerheblich bleibt, ob der Beschwerdeführer zur Angabe der entsprechenden Umstände verpflichtet war. Der Beschwerdeführer hatte daher Anlass, die Situation aufzuklären, und die Vorinstanz war nicht zu entsprechenden Nachfragen verpflichtet (vgl. dagegen zum Fall umfassender und klarer Angaben im Gesuch die Urteile 9C_568/2015 vom 16. Oktober 2015 E. 3.3; 5A_26/2008 vom 4. Februar 2008 E. 4.3).
Wenig überzeugend ist das Vorbringen des Beschwerdeführers, aus den vorhandenen Angaben lasse sich der Wegfall des fraglichen Einkommens bzw. eine entsprechende Erklärung (implizit) ableiten: Wie die Vorinstanz und die Verfahrensbeteiligte zutreffend einwenden, bestätigen die vorhandenen Akten die Vollständigkeit der Angaben des Beschwerdeführers gerade nicht.
3.4. Damit ist es nicht zu beanstanden, dass die Vorinstanz dem Beschwerdeführer das in seiner Höhe im Übrigen unbestrittene Einkommen aus einer Anstellung bei der E._ AG anrechnete und in der Folge den Bedürftigkeitsnachweis als nicht erbracht erachtete. Dabei ist nicht strittig, dass der Beschwerdeführer unter Berücksichtigung beider Erwerbseinkommen seine Prozesskosten bestreiten kann (vgl. E. 3.1 hiervor). Unbeachtlich bleibt in diesem Zusammenhang das vom Beschwerdeführer im bundesgerichtlichen Verfahren eingereichte Bestätigungsschreiben vom 21. Juni 2021 (Beschwerdebeilage 6), bei dem es sich um ein echtes Novum handelt (<ref-law>; <ref-ruling> E. 1.2; <ref-ruling> E. 3.1.2). Folglich konnte das Appellationsgericht das Gesuch des Beschwerdeführers ohne Verfassungsverletzung abweisen und erweist sich die Beschwerde als unbegründet. Auf die weitere Frage, ob dem Beschwerdeführer ausserdem noch ein Unterhaltsanspruch anzurechnen wäre, braucht nicht mehr eingegangen zu werden.
4.
Nach dem Ausgeführten ist die Beschwerde abzuweisen. Bei diesem Ausgang des Verfahrens sind die Gerichtskosten dem Beschwerdeführer aufzuerlegen (<ref-law>). Weder der Beschwerdeführer noch der Kanton Basel-Stadt sind zu entschädigen (Art. 68 Abs. 1-3 BGG). Der Verfahrensbeteiligten, die einzig mit ihrem Eventualantrag obsiegte, ist zu Lasten des Beschwerdeführers eine reduzierte Parteientschädigung zuzusprechen (vgl. Urteil 2C_123/2016 vom 21. November 2017 E. 8.2). Das Gesuch des Beschwerdeführers um unentgeltliche Rechtspflege und Verbeiständung im bundesgerichtlichen Verfahren - dieses wird im Übrigen nur sehr rudimentär begründet - ist abzuweisen, da die Beschwerde nach dem Ausgeführten als von vornherein aussichtslos beurteilt werden muss (Art. 64 Abs. 1 und 2 BGG).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen.
2.
Das Gesuch des Beschwerdeführers um unentgeltliche Rechtspflege im bundesgerichtlichen Verfahren wird abgewiesen.
3.
Die Gerichtskosten von Fr. 1'000.-- werden dem Beschwerdeführer auferlegt.
4.
Der Beschwerdeführer hat die B._, für das bundesgerichtliche Verfahren mit Fr. 500.-- zu entschädigen.
5.
Dieses Urteil wird den Parteien und der B._ schriftlich mitgeteilt.
Lausanne, 10. November 2021
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Das präsidiale Mitglied: Escher
Der Gerichtsschreiber: Sieber