Sachverhalt:
A.
X._ war nach der Trennung von seiner Ehefrau, mit welcher er in Y._/ZH wohnhaft war, zwischen dem 1. Mai 2005 und dem 15. Juli 2007 in Z._/SG gemeldet. Per 1. Januar 2006 mietete X._ ein Zimmer in A._/ZH. Am 15. Juli 2007 erfolgte die Abmeldung in Z._ unter Angabe des Wegzugs nach Mexiko, wobei sich X._ am 14. Juli 2008 in B._/ZH als von Mexiko herkommend anmeldete.
Die Staats- und Gemeindesteuern des Kantons St. Gallen wurden für die Steuerperioden 2005 bis und mit 15. Juli 2007 rechtskräftig veranlagt. Auf Meldung der Gemeinde B._ hin leiteten die zuständigen Behörden des Kantons St. Gallen im Verlaufe des Jahres 2009 Abklärungen zum Lebensmittelpunkt von X._ zwischen dem 16. Juli 2007 und dem 14. Juli 2008 ein.
B.
Mit Verfügung vom 1. Dezember 2009 stellte das Steueramt des Kantons St. Gallen fest, X._ sei für die Zeit vom 16. Juli 2007 bis 31. Dezember 2007 kraft persönlicher Zugehörigkeit im Kanton St. Gallen in der Gemeinde Z._ unbeschränkt steuerpflichtig. Die dagegen erhobene Einsprache wies das Steueramt des Kantons St. Gallen am 10. Mai 2010 ab. Anschliessend gelangte X._ an die Verwaltungsrekurskommission des Kantons St. Gallen, die den Rekurs mit Entscheid vom 8. Dezember 2011 abwies. Die dagegen erhobene Beschwerde wies das Verwaltungsgericht des Kantons St. Gallen am 13. November 2012 ab.
C.
Vor Bundesgericht beantragt X._ sinngemäss, das Urteil des Verwaltungsgerichts des Kantons St. Gallen vom 13. November 2012 aufzuheben und festzustellen, dass er für die Zeit vom 16. Juli 2007 bis 31. Dezember 2007 nicht im Kanton St. Gallen in der Gemeinde Z._ unbeschränkt steuerpflichtig sei, eventualiter die Sache an die Vorinstanz zurückzuweisen.
Das kantonale Steueramt des Kantons St. Gallen und das kantonale Steueramt des Kantons Zürich verzichteten auf eine Vernehmlassung, wobei letzteres darauf hinwies, dass X._ erst ab 14. Juli 2008 in das Steuerregister des Kantons Zürich aufgenommen wurde. Das Verwaltungsgericht des Kantons St. Gallen und die Eidgenössische Steuerverwaltung beantragen die Abweisung der Beschwerde.
D.
Der Beschwerdeführer hat am 21. März 2013 eine Replik eingereicht.

Erwägungen:
1.
1.1. Der Beschwerdeführer erhebt "staatsrechtliche Beschwerde und Beschwerde" gegen das Urteil des Verwaltungsgerichts des Kantons St. Gallen vom 13. November 2012. Die unrichtige Bezeichnung des Rechtsmittels als "staatsrechtliche Beschwerde" schadet nicht, sofern bezüglich des jeweils statthaften Rechtsmittels sämtliche Sachurteilsvoraussetzungen erfüllt sind (vgl. <ref-ruling> E. 1.2 S. 382; <ref-ruling> E. 3.1 S. 399; je mit Hinweisen). Beim angefochtenen Urteil handelt es sich um einen kantonal letztinstanzlichen Steuerdomizilentscheid, d.h. um eine Angelegenheit des öffentlichen Rechts, die unter keinen Ausschlussgrund gemäss <ref-law> fällt und gegen welche die Beschwerde in öffentlich-rechtlichen Angelegenheiten zulässig ist (vgl. Art. 82 lit. a i.V.m. <ref-law>). Der Beschwerdeführer ist gestützt auf <ref-law> beschwerdebefugt. Auf die im Übrigen form- und fristgerecht eingereichte Beschwerde ist daher grundsätzlich einzutreten.
1.2. 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), nur die geltend gemachten Vorbringen, falls allfällige weitere rechtliche Mängel nicht geradezu offensichtlich sind (<ref-ruling> E. 1.6 S. 280 mit Hinweis). Hinsichtlich der Verletzung von Grundrechten, darin eingeschlossen solcher, die sich aus Völkerrecht ergeben, gilt eine qualifizierte Rügepflicht (<ref-law>; <ref-ruling> E. 2 S. 76 f.; <ref-ruling> E. 5.2 S. 373, 274 E. 1.6 S. 280 f.).
1.3. Das Bundesgericht legt seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (<ref-law>). Es kann die vorinstanzliche Sachverhaltsfeststellung bloss berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law>). Die betroffene Person muss rechtsgenügend dartun, dass und inwiefern der festgestellte Sachverhalt in einem entscheidwesentlichen Punkt klar und eindeutig mangelhaft erscheint (Art. 97 Abs. 1 i.V.m. Art. 42 Abs. 2 und <ref-law>; vgl. <ref-ruling> E. 1.6 S. 281; <ref-ruling> E. 1.4 S. 336; <ref-ruling> E. 7.4 S. 230).
2.
2.1. Strittig ist vorliegend die subjektive Steuerpflicht infolge persönlicher Zugehörigkeit für die Periode vom 16. Juli 2007 bis 31. Dezember 2007. Ausserhalb des Streitgegenstandes liegt namentlich die subjektive Steuerpflicht für die Jahre 2005 bis 15. Juli 2007. Für diesen Zeitraum liegen rechtskräftige Veranlagungsentscheide vor.
2.2. Nach Auffassung der Vorinstanz ist es Sache des Beschwerdeführers nachzuweisen, dass er in der Periode vom 16. Juli 2007 bis 31. Dezember 2007 im Ausland oder in einem anderen Kanton einen neuen Wohnsitz begründet hat. Da dieser Nachweis dem Beschwerdeführer nicht gelungen sei, bestehe der bisherige Wohnsitz in Z._ auch in der Zeit vom 16. Juli 2007 bis 31. Dezember 2007 fort.
2.3. Der Beschwerdeführer macht geltend, sein Wohnsitz habe sich in der hier strittigen Periode im Ausland oder - wenn überhaupt in der Schweiz - in A._ befunden. Die Vorinstanz gehe von einer "Wohnsitzfiktion" aus, für die es keine gesetzliche Grundlage gebe und die gegen grund- und menschenrechtliche Garantien (<ref-law>; <ref-law>; <ref-law>; Art. 14 EMRK) sowie gegen völkerrechtliche Verpflichtungen in den einschlägigen Doppelbesteuerungsabkommen und dem Wiener Übereinkommen vom 23. Mai 1969 über das Recht der Verträge (Wiener Übereinkommen, VRK; SR 0.111) verstosse. Auch widerspreche die vorgenommene Beweislastverteilung den Ansprüchen auf ein faires Verfahren (<ref-law>; Art. 6 EMRK).
3.
3.1. Gemäss <ref-law>, Art. 3 Abs. 1 StHG sowie Art. 13 Abs. 1 des Steuergesetzes des Kantons St. Gallen vom 9. April 1998 (sGS 811.1; nachfolgend: StG/SG) sind natürliche Personen aufgrund persönlicher Zugehörigkeit steuerpflichtig, wenn sie ihren steuerrechtlichen Wohnsitz oder Aufenthalt in der Schweiz bzw. im Kanton haben. Einen steuerrechtlichen Wohnsitz in der Schweiz bzw. im Kanton hat eine natürliche Person namentlich, wenn sie sich hier mit der Absicht dauernden Verbleibens aufhält (<ref-law>; Art. 3 Abs. 2 StHG; Art. 13 Abs. 2 StG/SG; vgl. auch <ref-law>). Der Begriff des steuerrechtlichen Wohnsitzes setzt sich damit aus einem objektiven, äusseren (Aufenthalt) und einem subjektiven, inneren Element (Absicht) zusammen (Urteil 2C_627/2011, 2C_653/2011 vom 7. März 2012 E. 4.1, in: StE 2012 A 31.2 Nr. 10).
3.2. Der steuerrechtliche Wohnsitz einer Person befindet sich dort, wo faktisch der Mittelpunkt ihrer Lebensinteressen liegt ("le lieu où se situe le centre de ses intérêts"; <ref-ruling> E. 4.1 S. 36; <ref-ruling> E. 2 S. 56; <ref-ruling> E. 2a S. 293 f.). Dabei ist von objektiven, äusseren Umständen auf innere Tatsachen zu schliessen (vgl. zum Ganzen Urteil 2C_92/2012 vom 17. August 2012 E. 4.1, in: StE 2013 A 24.21 Nr. 24). Darüber kann gemeinhin kein klarer Beweis geführt werden, sondern es ist aufgrund von Indizien eine Gewichtung vorzunehmen. Hierzu ist eine sorgfältige Berücksichtigung und Gewichtung sämtlicher Berufs-, Familien- und Lebensumstände notwendig (Urteile 2C_397/2010 vom 6. Dezember 2010 E. 2.4.2, in: StE 2011 A 24.21 Nr. 22; 2C_646/2007 vom 7. Mai 2008 E. 4.3.3). Auf die bloss geäusserten Wünsche der steuerpflichtigen Person oder die gefühlsmässige Bevorzugung eines Ortes kommt es nicht an. Der steuerrechtliche Wohnsitz ist insofern nicht frei wählbar. Gleichermassen spielt das polizeiliche Domizil, an welchem die Schriften hinterlegt sind oder wo die politischen Rechte ausgeübt werden, keine entscheidende Rolle. Als äussere Merkmale können sie ein Indiz für den steuerrechtlichen Wohnsitz bilden, falls auch das übrige Verhalten der Person dafür spricht (<ref-ruling> E. 4.1 S. 35 f.; zum Registerrecht Urteil 2C_919/2011 vom 9. Februar 2012 E. 3.2, mit Hinweisen). Pflegt eine Person Kontakte zu mehreren Orten, ist für die Bestimmung des steuerrechtlichen Wohnsitzes darauf abzustellen, zu welchem Ort sie die stärkeren Beziehungen unterhält. Dabei ist diese Frage jeweils aufgrund der Gesamtheit der Umstände des Einzelfalls zu beurteilen (<ref-ruling> E. 4.2 S. 36 f., mit Hinweisen).
3.3. Im internationalen Verhältnis ist darüber hinaus <ref-law> analog anwendbar: Der einmal begründete Wohnsitz in der Schweiz bleibt grundsätzlich bis zum Erwerb eines neuen Wohnsitzes im Ausland bestehen (sog. "rémanence du domicile"; <ref-ruling> E. 3.3 S. 306; Urteil 2C_452/2012, 2C_453/2012 vom 7. November 2012 E. 4, in: StE 2013 A 32 Nr. 19; 2C_111/2012 vom 25. Juli 2012 E. 4.3). Im interkantonalen Verhältnis greift die Regelung des <ref-law> dagegen nicht (Urteile 2C_827/2008 vom 16. Juni 2009 E. 3.2; 2P.5/2007 vom 22. Februar 2008 E. 2.2.1, in: StE 2009 A 24.22 Nr. 6; 2A.475/2003 vom 26. Juli 2004 E. 2.1 und 2.2, in: RDAF 2005 II S. 103; KURT LOCHER/PETER LOCHER, Die Praxis der Bundessteuern, III. Teil, Das interkantonale Doppelbesteuerungsrecht, § 3, I A, 2c Nr. 1-5). Hat die steuerpflichtige Person die Verbindungen zu ihrem bisherigen Wohnsitz gelöst, so ist sie dort nicht mehr steuerpflichtig ( LOCHER/LOCHER, a.a.O., § 3, I A, 1 Nr. 14).
3.4. Davon zu unterscheiden ist die beweisrechtliche Frage, ob der Nachweis der Wohnsitzverlegung erbracht worden ist. Grundsätzlich ist die subjektive Steuerpflicht als steuerbegründende Tatsache von der Steuerbehörde nachzuweisen (Urteil 2C_92/2012 vom 17. August 2012 E. 4.3, in: StE 2013 A 24.21 Nr. 24, mit Hinweisen). Der steuerpflichtigen Person kann jedoch auch im interkantonalen Verhältnis der Beweis für die von ihr behauptete subjektive Steuerpflicht an einem neuen Ort auferlegt werden, sofern die von der Steuerbehörde angenommene bisherige subjektive Steuerpflicht in der strittigen Steuerperiode als sehr wahrscheinlich erscheint (Urteile 2C_672/2010 vom 30. Juni 2011 E. 4.2; 2C_625/2009 vom 16. Februar 2010 E. 3.2; 2C_827/2008 vom 16. Juni 2009 E. 4.1; ASA 39 284 E. 3c S. 288; LOCHER/LOCHER, a.a.O., § 3, I A, 1 Nr. 22). Wird der Nachweis der Wohnsitzverlegung nicht erbracht, ist das bisherige Domizil als fortbestehend zu betrachten (vgl. Urteile 2C_827/2008 vom 16. Juni 2009 E. 3.2; 2P.5/2007 vom 22. Februar 2008 E. 2.2.1, in: StE 2009 A 24.22 Nr. 6; 2P.186/2004 vom 15. Februar 2005 E. 2.3; LOCHER/LOCHER, a.a.O., § 3, IA, 2b Nr. 4). Ob eine bestimmte Tatsache bewiesen ist, ist Tatfrage, während die Beweislastverteilung Rechtsfrage ist (vgl. <ref-ruling> E. 5 S. 327; zum Steuerdomizil: Urteil 2C_111/2012 vom 25. Juli 2012 E. 4.4 in fine).
4.
4.1. Gemäss den vorinstanzlichen Feststellungen hat der Beschwerdeführer den Nachweis für einen neuen Wohnsitz im Ausland nicht erbracht. Der Beschwerdeführer hielt sich zwar in der Zeit vom 16. Juli 2007 bis 14. Juli 2008 aufgrund seiner beruflichen Tätigkeit unstrittig in Kanada, Mexiko und den USA auf, doch fehlen Belege dafür, dass er in einem dieser Länder einen Wohnsitz begründet hat. Namentlich gibt es keinen Nachweis dafür, dass sich der Beschwerdeführer, wie von ihm behauptet, tatsächlich in Las Vegas (USA) aufgehalten hat. Dabei ist das Verwaltungsgericht zu Recht davon ausgegangen, dass sich die dem interkantonalen Doppelbesteuerungsrecht bekannte Sonderregelung für leitende Angestellte nicht auf internationale Verhältnisse übertragen lässt (Urteil 2C_452/2012, 2C_453/2012 vom 7. November 2012 E. 4.6, in: StE 2013 A 32 Nr. 19). Der Beschwerdeführer legt nicht rechtsgenüglich dar, inwiefern die vorinstanzlichen Sachverhaltsfeststellungen offensichtlich unrichtig sein sollen (Art. 97 und 105 BGG). Es ist daher mit der Vorinstanz von einem bloss vorübergehenden Auslandaufenthalt in der Zeit vom 16. Juli 2007 bis 14. Juli 2008 auszugehen. Angesichts dieser Umstände durfte die Vorinstanz davon ausgehen, dass der Wohnsitz in Z._ in der strittigen Periode fortdauerte (vgl. <ref-law> analog).
4.2.
4.2.1. Auch die Behauptung des Beschwerdeführers, sein Wohnsitz befinde sich - wenn überhaupt in der Schweiz - in A._, verfängt nicht. Der Beschwerdeführer wendet hauptsächlich ein, er habe gar nie in Z._ Wohnsitz genommen. Wie die Vorinstanz zu Recht ausführt, setzt sich der Beschwerdeführer damit zu seinem eigenen Verhalten in Widerspruch, war er doch zwischen dem 1. Mai 2005 und dem 15. Juli 2007 in Z._ angemeldet, verfügte dort über eine Wohnstätte und liess sich mit Steuererklärungen vom 3. Juli 2006, 21. Juni 2007 und 5. Juli 2007 für die Steuerperioden 2005, 2006 und 2007 (bis 15. Juli 2007) jeweils anstandslos auf das Veranlagungsverfahren in Z._ ein. Dabei zog der Beschwerdeführer die Kosten für das Zimmer in A._, wo er sich nie angemeldet hatte, als Mehrkosten bei auswärtigem Wochenaufenthalt ab. Erst in den Einspracheverfahren vom 14. Juli 2007 bzw. 22. November 2007 brachte der Beschwerdeführer vor, sein Wohnsitz befinde sich in A._, wobei er schliesslich für die Jahre 2005 bis 15. Juli 2007 rechtskräftig in Z._ veranlagt wurde.
4.2.2. Bei dieser Ausgangslage (Verhalten des Beschwerdeführers, rechtskräftige Veranlagungen für die Jahre 2005 bis 15. Juli 2007, vorübergehender Auslandaufenthalt ab 16. Juli 2007) ist es Sache des Beschwerdeführers nachzuweisen, dass in der strittigen Periode eine Wohnsitzverlegung nach A._ stattgefunden hat. Wie die Vorinstanz hierzu festgehalten hat, vermögen die vom Beschwerdeführer aufgelegten Belege keine engen Beziehungen zur Gemeinde A._ in der Zeit vom 16. Juli 2007 bis 31. Dezember 2007 zu belegen. Auch ist eine leitende Stellung des Beschwerdeführers bei Ausübung seiner unselbständigen Erwerbstätigkeit (vgl. <ref-ruling> E. 4.3 S. 37 f.) nicht erstellt. Inwiefern diese Feststellungen offensichtlich unrichtig sein sollen, legt der Beschwerdeführer nicht rechtsgenüglich dar (Art. 97 und 105 BGG). Infolgedessen ist der Schluss der Vorinstanz, dass sich der Beschwerdeführer in der strittigen Periode nicht mit der Absicht weiteren Verbleibens in A._ aufgehalten hat, nicht zu beanstanden.
4.3. Damit erweist die Beendigung der subjektiven Steuerpflicht per 15. Juli 2007 im Nachhinein als verfrüht, da der Auslandaufenthalt nur vorübergehend war. Dass der Beschwerdeführer seine Verbindungen zum bisherigen Wohnsitz in Z._ aufgeben wird, zeigte sich erst durch die (unstrittige) Wohnsitznahme in B._ per 14. Juli 2008. Ist der Nachweis der Wohnsitzaufgabe in Z._ in der hier strittigen Periode somit nicht erbracht, ist das bisherige Steuerdomizil als fortbestehend zu betrachten, womit der Beschwerdeführer für die Zeit vom 16. Juli 2007 bis 31. Dezember 2007 in Z._ kraft persönlicher Zugehörigkeit unbeschränkt steuerpflichtig ist. Folglich hat die Vorinstanz die Normen zur subjektiven Steuerpflicht korrekt angewandt, die Beweislast richtig verteilt und nicht in unzulässiger Weise auf eine blosse Wohnsitzfiktion abgestellt. Die diesbezüglichen Rügen des Beschwerdeführers gehen daher ins Leere. Im Übrigen findet Art. 6 EMRK auf das vorliegende Steuerverfahren keine Anwendung (<ref-ruling> E. 2.1 S. 146; Urteil 2C_455/2011, 2C_456/2011 vom 5. April 2012 E. 4.2).
5.
5.1. Schliesslich ist die vom Beschwerdeführer gerügte Verletzung der einschlägigen Doppelbesteuerungsabkommen nicht ersichtlich. Hierbei beruft er sich auf die Kollisionsregel (sog. "Tie-Breaker-Rule") des jeweiligen Art. 4 des Abkommens vom 3. August 1993 zwischen dem Schweizerischen Bundesrat und der Regierung der Vereinigten Staaten von Mexiko zur Vermeidung der Doppelbesteuerung auf dem Gebiet der Steuern vom Einkommen (DBA-MEX; SR 0.672.956.31) bzw. des Abkommens vom 2. Oktober 1996 zwischen der Schweizerischen Eidgenossenschaft und den Vereinigten Staaten von Amerika zur Vermeidung der Doppelbesteuerung auf dem Gebiete der Steuern vom Einkommen (DBA-USA; SR 0.672.933.61).
5.2. Voraussetzung zur Anwendung der angerufenen Kollisionsregeln in den Doppelbesteuerungsabkommen ist jedoch, dass eine Doppelansässigkeit vorliegt. Sie ist von der steuerpflichtigen Person geltend zu machen und nachzuweisen (vgl. Urteile 2C_452/2012, 2C_453/2012 vom 7. November 2012 E. 5.2, in: StE 2013 A 32 Nr. 19; 2C_472/2010 vom 18. Januar 2011 E. 3.3, in: StE 2011 A 32 Nr. 17; PETER LOCHER, Einführung in das internationale Steuerrecht der Schweiz, 3. Aufl. 2005, S. 244). Die Vorinstanz hat dazu für das Bundesgericht verbindlich (vgl. <ref-law>) festgestellt, dass der Beschwerdeführer keinen Nachweis dafür erbracht hat, dass er im Ausland Steuern bezahlt hat oder dort von der Steuerpflicht befreit worden ist. Insoweit ist eine Doppelansässigkeit nicht erstellt, womit die angerufenen Kollisionsregeln nicht zur Anwendung gelangen.
6.
Aus dem Gesagten folgt, dass die Beschwerde abzuweisen ist. Dem Verfahrensausgang entsprechend wird der unterliegende Beschwerdeführer kostenpflichtig (vgl. <ref-law>). Es sind keine Parteientschädigungen geschuldet (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen.
2.
Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdeführer auferlegt.
3.
Dieses Urteil wird den Verfahrensbeteiligten, dem Verwaltungsgericht des Kantons St. Gallen und der Eidgenössischen Steuerverwaltung schriftlich mitgeteilt.
Lausanne, 1. Juli 2013
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Zünd
Der Gerichtsschreiber: Egli