Sachverhalt:
A.
A.a. Am 2. Februar 2013 entwendete eine unbekannte Täterschaft in zwei Supermärkten im Kanton St. Gallen die Portemonnaies von A._ und B._ und bezog an Geldautomaten insgesamt Fr. 4'500.--. Weitere Versuche, mit einer Mastercard zweimal Fr. 1'000.-- und einmal Fr. 3'000.-- abzuheben, blieben erfolglos.
A.b. Die Auswertung des bei den Geldbezügen aufgezeichneten Bildmaterials ergab, dass es sich um denselben Täter handelte. Die Kantonspolizei St. Gallen verbreitete die Bilder per nationalem Fahndungsersuchen. Rückmeldungen kantonaler Polizeikorps ergaben, dass der Täter weiterer Delikte gleichen Schemas verdächtigt wurde. Am 28. März 2013 ersuchte das Untersuchungsamt Gossau die Staatsanwaltschaft des Kantons Solothurn um Verfahrensübernahme mit dem Hinweis, dass es sich gemäss Mitteilung der Kriminalpolizei Schaffhausen vom 22. Februar 2013 bei der Täterschaft um X._ handle. Die Staatsanwaltschaft des Kantons Solothurn verzichtete nach Aktenstudium auf die Eröffnung einer Strafuntersuchung gegen X._. Aufgrund der zur Verfügung stehenden Fotos könne festgehalten werden, dass der Täter vom 2. Februar 2013 dieselbe Person sei, gegen die im Kanton Solothurn bereits ermittelt werde. Dass es sich hierbei um X._ handle, werde stark angezweifelt. Weder die Lippen- und Nasenform noch die Augenbrauenpartie stimmten mit dem Täter überein. Einzig gestützt auf das Foto dränge sich kein Anfangsverdacht gegen X._ auf. Bei gegenteiliger Auffassung sei die für Gerichtsstände zuständige stellvertretende Oberstaatsanwältin zu kontaktieren.
A.c. Das Untersuchungsamt Gossau ersuchte am 17. April und 2. Juli 2013 die Staatsanwaltschaft des Kantons Zürich um rechtshilfeweise Befragung von X._. Am 12. Juli 2013 ordnete sie auf Antrag der Kantonspolizei Zürich eine Hausdurchsuchung an dessen Wohnort an, die am frühen Morgen des 16. Juli 2013 stattfand. Gleichentags wurde X._ polizeilich einvernommen. Er konnte anhand seines Passes nachweisen, dass er zur Tatzeit in Brasilien war.
A.d. Am 8. August 2013 stellte die Staatsanwaltschaft des Kantons St. Gallen das Strafverfahren gegen X._ ein und wies das von ihm gestellte Genugtuungsbegehren von Fr. 1'000.-- ab.
B.
Die hiergegen erhobene Beschwerde wies die Anklagekammer des Kantons St. Gallen am 18. September 2013 ab.
C.
X._ führt Beschwerde in Strafsachen und beantragt, der Entscheid der Anklagekammer sei aufzuheben, und ihm sei eine angemessene Genugtuung auszurichten. Eventuell sei die Sache an die Vorinstanz zurückzuweisen. Subeventuell seien im Fall der Beschwerdeabweisung die vorinstanzlichen Kosten angemessen zu reduzieren. X._ ersucht um aufschiebende Wirkung seiner Beschwerde.
D.
Die Staatsanwaltschaft des Kantons St. Gallen beantragt, das Gesuch um aufschiebende Wirkung und die Beschwerde abzuweisen. Sie macht für das Beschwerdeverfahren vor Bundesgericht eine Gebühr von Fr. 500.-- geltend. Die Anklagekammer erhebt keine Einwände gegen das Gesuch um aufschiebende Wirkung. Auf eine Vernehmlassung zur Beschwerde hat sie verzichtet.
E.
Am 12. November 2013 erteilte das präsidierende Mitglied der strafrechtlichen Abteilung der Beschwerde aufschiebende Wirkung.

Erwägungen:
1.
1.1. Der Beschwerdeführer rügt eine Verletzung von <ref-law>, <ref-law> und <ref-law>. Die Hausdurchsuchung sei mangels hinreichenden Tatverdachts und Wahrung des Verhältnismässigkeitsprinzips rechtswidrig. Die Bilder des Täters wiesen lediglich eine schwache Ähnlichkeit mit seinem Foto auf. Bei genauerem Hinsehen sei klar ersichtlich, dass die Nasenformen nicht übereinstimmten. Die Strafverfolgungsbehörden wären verpflichtet gewesen, ihn vor der Anordnung der Hausdurchsuchung zu befragen. Dies hätte gezeigt, dass er aufgrund seines Auslandsaufenthaltes nicht der Täter sein könne. Die Hausdurchsuchung stelle einen schweren Eingriff in sein Hausrecht und die persönlichen Verhältnisse dar. Die Bewohner des Wohnquartiers, die sich alle persönlich kennen würden, hätten die Hausdurchsuchung mitbekommen, was besonders peinlich gewesen sei.
1.2. Die Vorinstanz erwägt, die Beschwerdegegnerin verneine einen Genugtuungsanspruch zu Recht. Es sei nicht ersichtlich, inwiefern die Durchführung einer im Sinne von <ref-law> rechtmässig angeordneten Hausdurchsuchung eine besonders schwere Persönlichkeitsverletzung darstellen solle. Mit der ohne Vorankündigung und vor Befragung durchgeführten Hausdurchsuchung hätte verhindert werden können, dass allfällig sicherzustellende Gegenstände wie die vom Täter bei den Geldbezügen getragene Kleidung beseitigt wurden. Die Durchsuchung habe (nur) von 6.20 Uhr bis 7.00 Uhr im Hausinneren stattgefunden, weshalb die Nachbarschaft diese kaum habe mitverfolgen können. Zwar sei das von der Durchsuchung betroffene Hausrecht ein elementares Grundrecht, jedoch stelle die rechtmässig angeordnete strafprozessuale Zwangsmassnahme für sich allein noch keine schwere Verletzung der persönlichen Verhältnisse im Sinne von <ref-law> oder <ref-law> dar.
1.3.
1.3.1. Gemäss <ref-law> können Zwangsmassnahmen (Art. 196-298 StPO) nur ergriffen werden, wenn sie gesetzlich vorgesehen sind, ein hinreichender Tatverdacht vorliegt, die damit angestrebten Ziele nicht durch mildere Massnahmen erreicht werden können und die Bedeutung der Straftat die Zwangsmassnahme rechtfertigt. Zwangsmassnahmen, die in die Grundrechte nicht beschuldigter Personen eingreifen, sind besonders zurückhaltend einzusetzen (<ref-law>). Gemäss <ref-law> können die Staatsanwaltschaft, die Gerichte - in dringenden Fällen deren Verfahrensleitung - sowie die Polizei in den gesetzlich vorgesehenen Fällen Zwangsmassnahmen anordnen.
Der Begriff des "hinreichenden Tatverdachts" stellt einen auslegungsbedürftigen unbestimmten Rechtsbegriff dar, bei dessen Anwendung der Sachrichter über einen weiten Ermessensspielraum verfügt. Das Bundesgericht prüft die vorinstanzliche Begriffsauslegung nur mit Zurückhaltung (<ref-ruling> E. 3.2; Urteil 1C_458/2013 vom 21. November 2013 E. 2.2 mit Hinweisen).
1.3.2. Die Vorinstanz geht auf die bereits im Beschwerdeverfahren erhobenen Vorbringen des Beschwerdeführers, es bestehe kein hinreichender Tatverdacht, da auf den Fotos klar ersichtlich sei, dass keine Ähnlichkeit zwischen ihm und dem Täter bestehe, nicht ein. Sie hält in Anlehnung an die staatsanwaltliche Einstellungsverfügung fest, die Hausdurchsuchung sei rechtmässig gewesen, ohne sämtliche materiellen Voraussetzungen von <ref-law> zu prüfen und zu begründen. Dies erweist sich als bundesrechtswidrig. Aufgrund des Schreibens der Staatsanwaltschaft des Kantons Solothurn vom 15. April 2013 und der Weigerung, eine Strafuntersuchung gegen den Beschwerdeführer zu eröffnen, bestanden erhebliche Zweifel hinsichtlich eines hinreichenden Tatverdachts. Die Staatsanwaltschaft Solothurn weist zutreffend darauf hin, dass sich aufgrund des von verschiedenen Kantonen übermittelten Bildmaterials kein Anfangsverdacht gegen den Beschwerdeführer aufdränge. Dessen Lippen- und Nasenform sowie die Augenbrauenpartie unterscheiden sich deutlich von denjenigen des Täters. Hals- und Kinnpartie des Täters sind wesentlich fülliger, und er hat - im Gegensatz zum Beschwerdeführer - lediglich rechts einen Ohrring. Ein hinreichender Tatverdacht im Sinne von <ref-law> lässt sich aufgrund der Aktenlage nicht begründen. Die Hausdurchsuchung erweist sich als rechtswidrig.
1.4. Auf den Antrag des Beschwerdeführers, ihm eine angemessene Genugtuung auszurichten, ist nicht einzutreten. Die Genugtuung besteht in der Regel in der Leistung einer Geldsumme (<ref-law>). Anstatt oder neben dieser Leistung kann der Richter auch auf eine andere Art der Genugtuung erkennen (<ref-law>; vgl. Urteil 5A_309/2013 vom 4. November 2013 E. 6.3.1). Die Festsetzung der Genugtuung ist eine Entscheidung nach Billigkeit und beruht auf richterlichem Ermessen (<ref-law>). Die Vorinstanz hat Art und Umfang der gemäss <ref-law> zuzusprechenden Genugtuung noch nicht geprüft. Es ist nicht Aufgabe des Bundesgerichts, dem Ermessensentscheid des Sachgerichts vorzugreifen.
1.5. Die Beschwerde ist gutzuheissen und zu neuer Entscheidung an die Vorinstanz zurückzuweisen. Die Angemessenheit der vorinstanzlichen Verfahrensgebühr ist nicht mehr zu prüfen ist.
2.
Es sind keine Gerichtskosten zu erheben. Der Kanton St. Gallen hat den Beschwerdeführer für das bundesgerichtliche Verfahren angemessen zu entschädigen. Der Beschwerdegegnerin ist - unabhängig davon, dass sie mit ihren Anträgen unterliegt (<ref-law>) - weder eine Gebühr noch eine Entschädigung auszurichten (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen, der Entscheid der Anklagekammer des Kantons St. Gallen vom 18. September 2013 aufgehoben und die Sache zu neuer Entscheidung an die Vorinstanz zurückgewiesen.
2.
Es werden keine Gerichtskosten erhoben.
3.
Der Kanton St. Gallen hat dem Beschwerdeführer für das bundesgerichtliche Verfahren eine Parteientschädigung von Fr. 2'000.-- auszurichten.
4.
Dieses Urteil wird dem Beschwerdeführer, der Staatsanwaltschaft des Kantons St. Gallen, Untersuchungsamt Gossau, und der Anklagekammer des Kantons St. Gallen schriftlich mitgeteilt.
Lausanne, 13. März 2014
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Mathys
Der Gerichtsschreiber: Held