Sachverhalt:
A.
A._ (geb. 1974) arbeitete vom 1. März 2009 bis 31. August 2011 im Rahmen eines Auslandvertrages für die B._ AG in Saudi-Arabien. Zuvor und danach hatte A._ sein Steuerdomizil in U._/TG.
B.
Am 9. November 2011 erliess das Gemeindesteueramt U._ einen Steuerdomizilentscheid mit der Feststellung, A._ sei auch für die Zeit nach dem 1. Januar 2009 bis zum Entscheiddatum unbeschränkt dort steuerpflichtig. Auf Einsprache hin bestätigte das genannte Amt den Entscheid am 16. März 2012. Die dagegen erhobenen Rechtsmittel wies die Steuerrekurskommission des Kantons Thurgau in einem einzigen Entscheid am 5. Februar 2013 ab. Die anschliessende Beschwerde hiess das Verwaltungsgericht des Kantons Thurgau mit Urteil vom 5./26. Juni 2013 gut und stellte fest, dass A._ vom 1. März 2009 bis 31. August 2011 keinen steuerrechtlichen Wohnsitz in der Schweiz hatte. Das Verwaltungsgericht sprach A._ für das verwaltungsgerichtliche Verfahren eine Parteientschädigung von Fr. 3'200.-- (zzgl. MWST) zu, wies jedoch den Antrag um Zusprache einer Parteientschädigung für das Verfahren vor der Steuerverwaltung und der Rekursinstanz ab (vgl. Ziff. 3 des Urteils vom 5./26. Juni 2013).
C.
Vor Bundesgericht beantragt A._, Ziff. 3 des Dispositivs des Urteils des Verwaltungsgerichts des Kantons Thurgau vom 5./26. Juni 2013 insoweit aufzuheben, als ihm eine Parteientschädigung für das Verfahren vor der Steuerrekurskommission in der Höhe von Fr. 23'705.25 zuzusprechen sei, eventualiter die Sache an die Vorinstanz zurückzuweisen.
Die Steuerverwaltung des Kantons Thurgau beantragt die Abweisung der Beschwerde. Das Verwaltungsgericht des Kantons Thurgau hat keine Vernehmlassung eingereicht.

Erwägungen:
1.
1.1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten gegen den kantonal letztinstanzlichen Kostenentscheid in einer Steuersache ist zulässig (Art. 82 lit. a, Art. 86 Abs. 1 lit. d und Art. 90 BGG). Der Beschwerdeführer ist hierzu legitimiert (<ref-law>). Auf die im Übrigen form- und fristgerecht eingereichte Beschwerde ist daher grundsätzlich einzutreten.
1.2. Mit der Beschwerde kann eine Rechtsverletzung nach Art. 95 und 96 BGG gerügt werden. Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>), doch prüft es, unter Berücksichtigung der allgemeinen Rüge- und Begründungspflicht (Art. 42 Abs. 1 und 2 BGG), grundsätzlich nur die geltend gemachten Vorbringen, sofern allfällige weitere rechtliche Mängel nicht geradezu offensichtlich sind (<ref-ruling> E. 1.6 S. 280 f. mit Hinweis). Die Verletzung von Grundrechten sowie von kantonalem und interkantonalem Recht untersucht es in jedem Fall nur insoweit, als eine solche Rüge in der Beschwerde präzise vorgebracht und begründet worden ist (<ref-law>; <ref-ruling> E. 2.2 S. 232; <ref-ruling> E. 2.2 S. 246; <ref-ruling> E. 1.4.2 S. 254; Urteil 2C_124/2013 vom 25. November 2013 E. 1.6).
Das Bundesgericht prüft die Anwendung des harmonisierten kantonalen Steuerrechts durch die kantonalen Instanzen an sich mit freier Kognition, ebenso, wie es dies im Fall von Bundesrecht täte. In den Bereichen, in welchen das Steuerharmonisierungsgesetz den Kantonen einen gewissen Gestaltungsspielraum belässt, beschränkt sich die Kognition des Bundesgerichts indessen auf Willkür und unterliegt den erhöhten Rügeanforderungen des <ref-law> (<ref-ruling> E. 2 S. 210; <ref-ruling> E. 3.1 S. 205 f.; Urteil 2C_554/2013 / 2C_555/2013 vom 30. Januar 2014 E. 1.4 mit Hinweisen).
1.3. Das Bundesgericht legt seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (<ref-law>), es sei denn, dieser sei offensichtlich unrichtig oder beruhe auf einer Rechtsverletzung im Sinne von <ref-law> (<ref-law>; <ref-ruling> E. 10.1 S. 445; <ref-ruling> E. 1.6 S. 280 f.).
2.
2.1. Der Beschwerdeführer rügt eine willkürliche Anwendung von § 80 Abs. 2 des Gesetzes des Kantons Thurgau vom 23. Februar 1981 über die Verwaltungsrechtspflege (RB 170; nachfolgend: VRG/TG). Die Bestimmung lautet wie folgt:
"Stehen sich in einem Rekursverfahren Privatparteien gegenüber, hat die obsiegende Privatpartei in der Regel Anspruch auf Ersatz der ausseramtlichen Kosten durch die unterliegende Privatpartei. Im Übrigen wird Ersatz ausseramtlicher Kosten nur zugesprochen, wenn sich dies bei komplizierter Sachlage oder schwierigen Rechtsfragen rechtfertigt."
2.2. Die Vorinstanz hat unter Anwendung dieser Bestimmung erwogen, vorliegend sei weder die Sachlage kompliziert, noch würden sich schwierige Rechtsfragen stellen. Die Frage des Steuerdomizils könne in der Regel auch von einem Laien unter Nachweis der üblichen Indizien nachgewiesen werden. Dass die Vorinstanzen zu einer unterschiedlichen Bewertung der sich stellenden Fragen gekommen seien, ändere daran nichts.
Der Beschwerdeführer bringt vor, vorliegend seien besondere Sach- und Rechtskenntnisse erforderlich gewesen. Die unzutreffende Fokussierung der Steuerverwaltung und der Steuerrekurskommission auf einzelne Sachverhaltsaspekte habe dazu geführt, dass es für einen Laien ohne Kenntnis der Rechtsprechung unmöglich gewesen sei, die für einen Wohnsitzwechsel in internationalen Verhältnissen erforderlichen rechtserheblichen Elemente zu erkennen. Es liege daher ein komplizierter Sachverhalt vor. Ebenso sei eine schwierige Rechtsfrage zu beantworten gewesen, da eine klare gesetzliche Regelung fehle und die kantonalen Instanzen unterschiedlicher Auffassung gewesen seien. Wenn selbst Fachinstanzen über den Wohnsitzwechsel nicht einig seien, führe dies zwingend zum Schluss, dass es sich um eine für einen juristischen Laien schwierige Rechtsfrage handeln müsse. Entsprechendes gelte für die Fragen der Mitwirkungspflicht und Beweislastverteilung.
2.3. Der Steuerdomizilentscheid betraf vorliegend unstrittig die direkte Bundessteuer wie die Staats- und Gemeindesteuern. Vorinstanz wie Beschwerdeführer haben offenbar übersehen, dass die Kostenverlegung vor der kantonalen Steuerrekurskommission im Bereich der direkten Bundessteuer in <ref-law> (SR 642.14) bundesrechtlich geregelt ist. Die Steuerrekurskommission hat denn auch im Entscheid vom 5. Februar 2013 ausdrücklich auf diese Norm hingewiesen. Das Harmonisierungsrecht enthält keine entsprechende Regelung, weshalb es im Bereich der Kantonssteuern Sache des kantonalen Rechts ist, eine entsprechende Ordnung vorzusehen (vgl. unten E. 4; Art. 50 des Bundesgesetzes vom 14. Dezember 1990 über die Harmonisierung der direkten Steuern der Kantone und Gemeinden [StHG; SR 642.14]; Urteil 2C_363/2009 vom 4. Februar 2010 E. 3.1).
Weder die Vorinstanz noch die Steuerrekurskommission haben bei der Regelung der Kosten- und Entschädigungsfolgen zwischen der direkten Bundessteuer und den kantonalen Steuern unterschieden. Aufgrund der unterschiedlichen Rechtsgrundlagen sowie des unterschiedlichen Prüfungsumfangs des Bundesgerichts bei Bundesrecht und kantonalem Recht ist jedoch eine getrennte Beurteilung der Zusprache bzw. Verweigerung der Parteientschädigung angezeigt (vgl. oben E. 1.2; dazu sinngemäss Urteil 2C_516/2013 / 2C_517/2013 vom 4. Februar 2014 E. 1.3).
3.
3.1. Im Bereich der direkten Bundessteuer verweist <ref-law> für die Zusprache von Parteikosten auf die einschlägigen Bestimmungen im VwVG (SR 172.021), gemäss welchen die Beschwerde- bzw. Rekursinstanz der ganz oder teilweise obsiegenden Partei von Amtes wegen oder auf Begehren eine Entschädigung für ihr erwachsene notwendige und verhältnismässig hohe Kosten zusprechen kann (<ref-law> i.V.m. <ref-law>). Die Höhe der Kosten des Verfahrens vor der kantonalen Steuerrekurskommission wird durch das kantonale Recht bestimmt (<ref-law> i.V.m. Art. 64 Abs. 1-3 VwVG e contrario; <ref-law>). Notwendig sind Parteikosten dann, wenn sie zur sachgerechten und wirksamen Rechtsverfolgung oder Rechtsverteidigung unerlässlich erscheinen (<ref-ruling> E. 7.2 S. 214; Urteil 2A.740/2005 vom 3. Januar 2006 E. 2.1). Der vom Gesetzgeber verwendete Begriff der "notwendigen und verhältnismässig hohen Kosten" gewährt der urteilenden Instanz einen erheblichen Beurteilungsspielraum. Sie hat ausgehend von den konkreten Umständen des Einzelfalles bzw. der jeweiligen Prozesslage frei zu würdigen, ob und in welcher Höhe eine Parteientschädigung geschuldet ist (<ref-ruling> E. 2 S. 509 ff.; Urteil 2A.468/2005 vom 7. April 2006 E. 3.2; ferner Urteile 8C_329/2011 vom 29. Juli 2011 E. 6.1; 9C_108/2010 vom 15. Juni 2010 E. 7.2).
Abweichend vom Wortlaut des § 80 Abs. 2 VRG/TG ist eine Parteientschädigung nach <ref-law> nicht nur bei komplizierter Sachlage oder schwierigen Rechtsfragen zuzusprechen. Entscheidend sind die Umstände des Einzelfalls. Wichtige Kriterien sind neben der Komplexität von Sach- und Rechtslage namentlich die in Frage stehenden Folgen für die steuerpflichtige Person, deren Fähigkeiten und prozessuale Erfahrungen sowie die Vorkehren der Behörden (Urteil 2A.58/1997 vom 17. November 1998 E. 3b mit Hinweisen; René Rhinow et al., Öffentliches Prozessrecht, 2. Aufl. 2010, Rz. 1700). Im Rahmen der Auslegung von <ref-law> wird in der Lehre die Auffassung vertreten, dass dem Bürger als der gegenüber der fachlich und juristisch versierten Behörde unterlegenen Partei in der Regel der Beizug eines rechtskundigen Vertreters ohne Weiteres zugestanden werden müsse (Marcel Maillard, in: Praxiskommentar VwVG, 2009, N. 26 zu <ref-law>; Martin Bernet, Die Parteientschädigung in der schweizerischen Verwaltungsrechtspflege, 1986, S. 148).
3.2. Das Verwaltungsgericht hat Bundesrecht verletzt (<ref-law>), indem es sich zu Unrecht alleine durch das kantonale Recht gebunden sah und das massgebliche eidgenössische Recht nicht anwandte. In der Folge hat die Vorinstanz den Beurteilungsspielraum nicht ausgeschöpft, der ihr durch <ref-law> i.V.m. <ref-law> aufgegeben ist.
3.3. Zu prüfen bleibt, ob dem Beschwerdeführer von Bundesrechts wegen ein Anspruch auf Parteientschädigung einzuräumen ist, dessen Höhe sich nach kantonalem Recht bemisst.
Wohl lässt sich die vorliegend in der Hauptsache zu beantwortende Rechtsfrage - der Lebensmittelpunkt des Beschwerdeführers vom 1. März 2009 bis 31. August 2011 - klar abgrenzen und bestimmen. Auch ist die Sachlage insofern nicht besonders komplex, als die erforderlichen Angaben zu den Berufs-, Familien- und Lebensumständen in der Regel von der steuerpflichtigen Person selbst beigebracht werden können und keine besonderen Beweisvorkehren erfordern. Indes zeigt die Behörden- und Gerichtspraxis, dass es mitunter schwerfällt zu beurteilen, wo sich der Lebensmittelpunkt der steuerpflichtigen Person befindet. Das ist wesentlich darauf zurückzuführen, dass von objektiven, äusseren Umständen auf innere Tatsachen geschlossen wird, worüber gemeinhin kein klarer Beweis geführt werden kann. Zu den offen gefassten gesetzlichen Begriffen (vgl. insb. <ref-law>; Art. 3 StHG) hat sich denn auch eine reichhaltige Rechtsprechung entwickelt, deren Kenntnis bei juristischen Laien nicht ohne Weiteres vorausgesetzt werden kann. Die steuerpflichtige Person muss jedoch um die Tragweite ihrer Mitwirkungspflicht und die rechtlich relevanten Umstände wissen, um ihren Rechtsstandpunkt wirksam darlegen und namentlich das Tatsachenfundament rechtzeitig in das Verfahren einbringen zu können. Jedenfalls in der vorliegend zu beurteilenden Konstellation erwies sich daher der Beizug eines Rechtsvertreters für das justizförmige Verfahren als notwendig im Sinne von <ref-law>.
Aus den genannten Gründen rechtfertigt es sich, dem Beschwerdeführer bereits im Verfahren vor der Steuerrekurskommission einen Rechtsvertreter beizugeben.
3.4. Zu beachten bleibt: Auch bei anerkanntermassen gerechtfertigter Vertretung können unnötige Kosten anfallen (Moser/Beusch/Kneubühler, Prozessieren vor dem Bundesverwaltungsgericht, 2. Aufl. 2013, Rz. 4.68 Fn. 200); entschädigt werden im Rahmen von <ref-law> nur die notwendigen Kosten (<ref-law> i.V.m. <ref-law>). Über die Bemessung der Parteientschädigung ist jedoch nicht im bundesgerichtlichen Verfahren zu entscheiden, zumal sich die Frage nach kantonalem Recht richtet (<ref-law>) und der urteilenden Behörde ein erheblicher Beurteilungsspielraum zusteht (vgl. oben E. 3.1; <ref-ruling> E. 1.3 S. 383 f.; Urteile 4A_375/2012 vom 20. November 2012 E. 1.2, nicht publ. in: <ref-ruling>; 8C_797/2010 vom 11. Januar 2011 E. 5.4).
4.
Für den Bereich der Staats- und Gemeindesteuern gilt § 80 Abs. 2 VRG/TG, wonach Ersatz ausseramtlicher Kosten nur zugesprochen wird, wenn sich dies bei komplizierter Sachlage oder schwierigen Rechtsfragen rechtfertigt (vgl. oben E. 2.1 und 2.3). Angesichts des harmonisierungsrechtlich eingeräumten Gestaltungsspielraums zugunsten der Kantone könnte das Bundesgericht im Wesentlichen nur eingreifen, wenn sich die Thurgauer Regelung zu den Kosten- und Entschädigungsfolgen als im Ergebnis geradezu unhaltbar bzw. willkürlich (<ref-law>) erweisen würde, was jedoch nicht zutrifft: Die wirksame Rechtsverteidigung kann zwar für juristische Laien in justizförmigen Verfahren den Beizug eines Rechtsvertreters nahelegen (vgl. oben E. 3.3). Damit geht jedoch nicht notwendigerweise ein Anspruch auf Parteientschädigung einher. Ein solcher Anspruch setzt grundsätzlich eine entsprechende gesetzliche Grundlage im anwendbaren Verfahrenserlass voraus (<ref-ruling> E. II/1/b S. 403 ff.; Urteile 2C_507/2013 vom 18. September 2013 E. 3.1; 1C_592/2012 vom 7. März 2013 E. 3.5; 2P.147/2005 vom 31. August 2005 E. 2). Einschlägig ist vorliegend § 80 Abs. 2 VRG/TG, wobei die Vorinstanz den Anspruch auf Parteientschädigung angesichts der klar definierten Rechtsfrage und der überblickbaren Sachlage willkürfrei verneinen durfte.
5.
5.1. Nach dem Gesagten erweist sich die Kostenbeschwerde als teilweise begründet. Der angefochtene Entscheid ist aufzuheben, soweit er - bezogen auf die direkte Bundessteuer - eine Parteientschädigung im Verfahren vor der Steuerrekurskommission verneint hat. Diesbezüglich ist die Sache zur Bemessung der Parteientschädigung an die Vorinstanz zurückzuweisen.
5.2. Der Beschwerdeführer dringt mit seinem Antrag nur teilweise durch. Bei diesem Verfahrensausgang rechtfertigt es sich, die Verfahrenskosten je hälftig dem Beschwerdeführer und dem Kanton Thurgau, der Vermögensinteressen verfolgt, aufzuerlegen (Art. 66 Abs. 1 und 4 BGG). Der Kanton Thurgau hat den Beschwerdeführer für das bundesgerichtliche Verfahren angemessen zu entschädigen, ohne selbst Anspruch auf eine Parteientschädigung zu haben (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird teilweise gutgeheissen. Der angefochtene Entscheid wird insoweit aufgehoben und die Sache zu neuer Entscheidung an die Vorinstanz zurückgewiesen, als dem Beschwerdeführer für das Bundessteuerverfahren vor der Steuerrekurskommission eine Parteientschädigung verweigert worden ist. Im Übrigen wird die Beschwerde abgewiesen.
2.
Die Gerichtskosten von Fr. 2'000.-- werden zu Fr. 1'000.-- dem Kanton Thurgau und zu Fr. 1'000.-- dem Beschwerdeführer auferlegt.
3.
Der Kanton Thurgau hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 1'000.-- zu entschädigen.
4.
Dieses Urteil wird den Verfahrensbeteiligten und dem Verwaltungsgericht des Kantons Thurgau schriftlich mitgeteilt.
Lausanne, 28. April 2014
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Das präsidierende Mitglied: Seiler
Der Gerichtsschreiber: Egli