Sachverhalt:
A.
Der senegalesische Staatsangehörige A._ (geb. 1. Juni 1984) weilte zwischen 2004 und 2006 als Mitglied einer afrikanischen Trommlergruppe gestützt auf vom Kanton St. Gallen ausgestellte Kurzaufenthaltsbewilligungen in der Schweiz. Am 31. Juli 2006 heiratete er die Schweizer Bürgerin B._ (geb. 3. November 1985). Das (damalige) Amt für Polizeiwesen und Zivilrecht des Kantons Graubünden erteilte A._ im Rahmen des Familiennachzugs eine Aufenthaltsbewilligung, die letztmals bis zum 30. Juli 2012 verlängert wurde.
B.
Am 7. April 2011 bzw. 11. August 2011 reichte A._ beim Amt für Migration und Zivilrecht des Kantons Graubünden ein Gesuch um Erteilung der Niederlassungsbewilligung ein. Nach Anhörung des Gesuchstellers und dessen Ehefrau verweigerte das Amt mit Verfügung vom 24. August 2012 die Verlängerung der Jahresaufenthaltsbewilligung und lehnte gleichzeitig das Gesuch um Erteilung der Niederlassungsbewilligung ab. Zur Begründung wurde ausgeführt, es fehle seit geraumer Zeit an einem ehelichen Zusammenleben in einem gemeinsamen Haushalt und es seien keine wichtigen Gründe für getrennte Wohnorte ersichtlich. Es bestünden auch keine Ansprüche nach Auflösung der Familiengemeinschaft.
Mit Entscheid des Bezirksgerichts Plessur vom 13. Dezember 2012 wurden die Eheleute A._ berechtigt, ab dem 1. März 2012 getrennt zu leben.
Die von A._ gegen die Verfügung des Amtes für Migration und Zivilrecht vom 24. August 2012 ergriffenen Rechtsmittel wurden vom Departement für Justiz, Sicherheit und Gesundheit des Kantons Graubünden (Entscheid vom 31. Januar 2013) und vom Verwaltungsgericht des Kantons Graubünden (Urteil vom 25. Februar 2014) abgewiesen.
C.
Mit Eingabe vom 30. April 2014 erhebt A._ Beschwerde in öffentlich-rechtlichen Angelegenheiten. Er beantragt, das Urteil des Verwaltungsgerichts des Kantons Graubünden vom 25. Februar 2014 sei - mit Ausnahme von Ziff. 2 (Gewährung der unentgeltlichen Rechtspflege) - aufzuheben und es sei dem Beschwerdeführer die Niederlassungsbewilligung zu erteilen bzw. es sei das Amt für Migration und Zivilrecht anzuweisen, dem Beschwerdeführer die Niederlassungsbewilligung zu erteilen. Eventualiter sei dem Beschwerdeführer die Jahresaufenthaltsbewilligung zu erteilen bzw. es sei das Amt für Migration und Zivilrecht anzuweisen, dem Beschwerdeführer die Jahresaufenthaltsbewilligung zu erteilen. Subeventualiter sei die Sache an die Vorinstanzen zur Neubeurteilung zurückzuweisen.
D.
Das Amt für Migration und Zivilrecht, das Departement für Justiz, Sicherheit und Gesundheit und das Verwaltungsgericht des Kantons Graubünden sowie das Bundesamt für Migration schliessen auf Abweisung der Beschwerde.
Mit Verfügung vom 6. Mai 2014 hat der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgerichts der Beschwerde antragsgemäss die aufschiebende Wirkung zuerkannt.

Erwägungen:
1.
Das Bundesgericht prüft seine Zuständigkeit und die Eintretensvoraussetzungen von Amtes wegen und mit freier Kognition (<ref-law>; <ref-ruling> E. 1.1 S. 3).
1.1. Gemäss <ref-law> ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht ausgeschlossen betreffend ausländerrechtliche Bewilligungen, auf die weder das Bundesrecht noch das Völkerrecht einen Anspruch einräumt.
Nach Art. 42 Abs. 1 des Bundesgesetzes vom 16. Dezember 2005 über die Ausländerinnen und Ausländer (Ausländergesetz, AuG; SR 142.20) haben ausländische Ehegatten von Schweizerinnen Anspruch auf Erteilung und Verlängerung der Aufenthaltsbewilligung, wobei vorausgesetzt wird, dass sie mit diesen zusammenwohnen. Art. 42 Abs. 3 AuG bestimmt sodann, dass die Ehegatten nach einem ordnungsgemässen und ununterbrochenen Aufenthalt von fünf Jahren Anspruch auf Erteilung der Niederlassungsbewilligung haben. Sodann hat der ausländische Ehegatte einer Schweizerin nach Auflösung der Ehe oder der Familiengemeinschaft u.a. dann weiterhin einen Anspruch auf Verlängerung der Aufenthaltsbewilligung, wenn die Ehegemeinschaft mindestens drei Jahre bestanden hat und eine erfolgreiche Integration besteht (Art. 50 Abs. 1 lit. a i.V.m. Art. 42 Abs. 1 AuG).
Auf diese Bestimmungen beruft sich der Beschwerdeführer und behauptet, dass die darin statuierten Anspruchsvoraussetzungen für die Erteilung der Niederlassungsbewilligung (Hauptantrag) bzw. der Jahresaufenthaltsbewilligung (Eventualantrag) erfüllt seien. Dies bedarf näherer Prüfung. Ob dem Beschwerdeführer tatsächlich eine Bewilligung zu erteilen ist, bildet Gegenstand der nachfolgenden materiellen Beurteilung (vgl. Urteile 2C_460/2009 vom 4. November 2009 E. 2.1.2, nicht publ. in: <ref-ruling>; 2C_304/2009 vom 9. Dezember 2009 E. 1.1, nicht publ. in: <ref-ruling>13). Auf die fristgerecht eingereichte Beschwerde in öffentlich-rechtlichen Angelegenheiten gegen den angefochtenen, kantonal letztinstanzlichen Endentscheid eines oberen Gerichts in einer Angelegenheit des öffentlichen Rechts (Art. 82 lit. a, Art. 86 Abs. 1 lit. d und Abs. 2, Art. 90 und Art. 100 Abs. 1 BGG) ist deshalb grundsätzlich einzutreten, zumal der Beschwerdeführer als Adressat des angefochtenen Entscheids ohne Weiteres zur Beschwerdeführung legitimiert ist (<ref-law>).
1.2. Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>). Es ist folglich weder an die in der Beschwerde geltend gemachten Argumente noch an die Erwägungen der Vorinstanz gebunden. Immerhin prüft das Bundesgericht, unter Berücksichtigung der allgemeinen Rüge- und Begründungspflicht (<ref-law>; vgl. <ref-ruling> E. 2.1 S. 245 f.), grundsätzlich nur die geltend gemachten Rügen, sofern die rechtlichen Mängel nicht geradezu offensichtlich sind (<ref-ruling> E. 1.4.1 S. 254). Eine qualifizierte Rügepflicht gilt u.a. hinsichtlich der Verletzung von Grundrechten. Das Bundesgericht prüft solche Rügen nur, wenn sie in der Beschwerde präzise vorgebracht und begründet worden sind (<ref-law>; vgl. <ref-ruling> E. 1.4.2 S. 254).
1.3. Das Bundesgericht stellt grundsätzlich auf den von der Vorinstanz festgestellten Sachverhalt ab (<ref-law>). Diese Sachverhaltsfeststellungen können vor Bundesgericht nur gerügt werden, wenn sie offensichtlich unrichtig sind oder auf einer Rechtsverletzung im Sinne von <ref-law> beruhen (Art. 97 Abs. 1 und Art. 105 Abs. 2 BGG). Die Rüge, der Sachverhalt sei offensichtlich unrichtig festgestellt worden, ist gleichbedeutend mit der Willkürrüge und muss daher gemäss den Anforderungen von <ref-law> in der Beschwerdeschrift begründet werden (<ref-ruling> E. 1.2.2 und E. 1.4.3 S. 252 ff.; <ref-ruling> E. 3 S. 351 f.). Vorausgesetzt ist zudem, dass die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>).
2.
2.1. Das Bundesgericht hat bereits in mehreren Entscheiden im Einklang mit der Literatur festgehalten, dass der Anspruch gemäss Art. 42 Abs. 3 AuG das Bestehen des ehelichen Zusammenlebens bzw. einer Haushaltsgemeinschaft während fünf Jahren voraussetzt (Urteile 2C_413/2013 vom 28. Juni 2013 E. 2.1; 2C_899/2011 vom 20. April 2012 E. 2.1; 2C_568/2011 vom 16. November 2011 E. 3.2; 2C_284/2011 vom 21. September 2011 E. 2.2; Martina Caroni, in: Caroni et al. [Hrsg.], Bundesgesetz über die Ausländerinnen und Ausländer, 2010, Rz. 55 zu Art. 42 AuG; Marc Spescha, in: Spescha/Thür/Zünd [Hrsg.], Migrationsrecht, 3. Aufl. 2012, Rz. 9 zu Art. 42 AuG).
2.2. Der Beschwerdeführer begründet den von ihm behaupteten Anspruch auf Erteilung der Niederlassungsbewilligung im Wesentlichen damit, dass er immer noch mit seiner Schweizer Ehefrau verheiratet sei und im Sinne von Art. 42 Abs. 3 AuG während mindestens fünf Jahren eine Haushaltsgemeinschaft mit seiner Ehefrau gebildet habe. Für allfällige Auslandabwesenheiten lägen bei beiden Ehegatten wichtige Gründe im Sinne von Art. 49 AuG (Ausnahmen vom Erfordernis des Zusammenwohnens) vor.
2.3. Die Vorinstanz ist dagegen der Auffassung, dass die Bedingung des Zusammenlebens für den Erhalt der Niederlassungsbewilligung schon seit 2008, spätestens aber seit Ende 2010 nicht mehr gegeben war (vgl. angefochtener Entscheid E. 2d). Sie stützt diese Auffassung auf einzelne Abwesenheiten der Ehegatten vom gemeinsamen Ehedomizil zwischen August 2006 und August 2011 und führt dazu aus, diese Abwesenheiten seien nicht von Art. 49 AuG gedeckt.
2.4. Wie die Vorinstanz zu Recht festgestellt hat, erreichte der Beschwerdeführer die Fünfjahresfrist gemäss Art. 42 Abs. 3 AuG am 1. August 2011, da die Ehe am 31. Juli 2006 geschlossen worden war. Zu prüfen ist deshalb im Folgenden, ob für diese fünfjährige Periode die Voraussetzungen eines ordnungsgemässen und ununterbrochenen Aufenthalts gegeben sind.
2.4.1. Die Vorinstanz hat sich für ihren abschlägigen Entscheid insbesondere auf die Befragungsprotokolle des Migrationsamtes abgestützt (vgl. angefochtener Entscheid 2c). Darin gab die Ehefrau zu Protokoll, sie hätten bereits seit anfangs 2008 mit erheblichen ehelichen Schwierigkeiten gekämpft. Ihre Weiterbildung und Auslandaufenthalte liessen ein normales Familienleben gar nicht zu. Sie sei im Jahr 2010 mehrere Monate in den USA und in Paris gewesen. Auch ihr Ehemann sei häufig für mehrere Wochen in den Senegal gereist. Kurz vor ihrer Abreise in die USA Ende August 2011 sei ihr Ehemann aus der ehelichen Wohnung ausgezogen. Der Beschwerdeführer gab seinerseits im Juni 2012 zu Protokoll, er sei unter anderem vom September bis Oktober 2010 sowie vom Dezember 2010 bis Februar 2011 im Senegal gewesen. Sie seien beide viel unterwegs und wenn er nach Hause komme, habe er keine Lust mehr, nach U._ zu fahren, sondern übernachte bei seinem Bruder in Chur.
2.4.2. Auch wenn die Aussagen in den Protokollen nicht alle eindeutig und widerspruchsfrei sind, durfte die Vorinstanz insgesamt doch den Schluss ziehen, dass aufgrund der zahlreichen Auslandaufenthalte und Abwesenheiten des Beschwerdeführers bzw. seiner Ehefrau hier nicht von einem ununterbrochenen Aufenthalt von fünf Jahren im Sinne von Art. 42 Abs. 3 AuG ausgegangen werden kann. Insbesondere hat die Vorinstanz zu Recht auch den - vom Beschwerdeführer nicht bestrittenen - Umstand gewürdigt, dass die Ehefrau bereits im Dezember 2010 beim zuständigen Amt nachfragte, ob dem Beschwerdeführer auch eine Niederlassungsbewilligung erteilt werden könne, obschon sie von ihm getrennt lebe.
2.4.3. Entgegen der Auffassung des Beschwerdeführers vermag auch der Eheschutzentscheid des Bezirksgerichts Plessur vom 13. Dezember 2012 daran nichts zu ändern: Zwar hat die Einzelrichterin darin ausgeführt, dass der Beschwerdeführer und seine Ehefrau zwischen dem ersten, zurückgezogenen Eheschutzgesuch vom 9. März 2011 und dem zweiten Eheschutzgesuch vom 5. November 2012 wieder zusammengelebt hätten und deshalb der Trennungszeitpunkt auf den 1. März 2012 festzulegen sei. Damit ist aber nicht verbindlich gesagt, ob in der relevanten Periode vom August 2006 bis August 2011 ein eheliches Zusammenleben ohne Unterbrüche stattgefunden hat. Auch aus dem Schreiben der Mutter der Ehefrau vom 10. April 2011, in dem diese ausführt, ihre Tochter und deren Ehemann könnten bei ihr im gemieteten Haus in U._ wohnen, lässt nicht ableiten, dass der Beschwerdeführer und seine Ehefrau während mindestens fünf Jahren eine ununterbrochene Haushaltsgemeinschaft gebildet haben.
2.4.4. Ein Anspruch des Beschwerdeführers auf Erteilung der Niederlassungsbewilligung wäre nach dem Ausgeführten somit nur dann vorstellbar, wenn die in Art. 49 AuG vorgesehene Ausnahme vom Erfordernis des Zusammenwohnens zur Anwendung gelangt, d.h. wenn wichtige Gründe für das Getrenntleben der Ehegatten bei gleichzeitigem Fortbestand der Familiengemeinschaft vorlagen, wozu insbesondere berufliche Verpflichtungen oder eine vorübergehende Trennung wegen erheblicher familiärer Probleme gehören (Art. 76 der Verordnung vom 24. Oktober 2007 über Zulassung, Aufenthalt und Erwerbstätigkeit [VZAE; SR 142.201]).
In diesem Zusammenhang hat die Vorinstanz festgestellt, dass weder für die Abwesenheiten des Beschwerdeführers im Senegal noch für die Auslandsaufenthalte seiner Ehefrau in den USA bzw. Paris berufliche Notwendigkeiten ersichtlich bzw. belegt seien. Der Beschwerdeführer macht zwar geltend, dass er mit seiner Musikgruppe "regelmässige Auftritte im Ausland" und seine Ehefrau als Tänzerin und Mitarbeiterin des Zirkus D._ "verschiedene Auftritte im Ausland" hatte. Praxisgemäss ist jedoch nicht jeder berufliche Grund ein wichtiger Grund (Urteil 2C_544/2010 vom 23. Dezember 2010 E. 2.3.1). Vielmehr müssen die Gründe objektivierbar sein und ein gewisses Gewicht aufweisen, was grundsätzlich von der ausländischen Person darzutun ist (Art. 90 AuG; Urteile 2C_428/2013 vom 8. September 2013 E. 4.2; 2C_340/2013 vom 28. Juni 2013 E. 2.2). Von einem wichtigen Grund kann desto eher gesprochen werden, je weniger die Ehegatten auf die Situation des Getrenntlebens Einfluss nehmen können, ohne einen grossen Nachteil in Kauf nehmen zu müssen (Urteil 2C_544/2010 vom 23. Dezember 2010 E. 2.3.1). Diese Anforderungen sind im vorliegenden Fall nicht erfüllt: Weder kann der Beschwerdeführer konkret belegen, dass er mit seiner Musikgruppe im Ausland für Konzerte im Ausland engagiert war noch lässt sich aus dem Tourneeplan des Zirkus auf berufsbedingt notwendige Abwesenheiten seiner Ehefrau schliessen. In diesem Zusammenhang erweist sich somit der Vorwurf der unrichtigen Sachverhaltsfeststellung bzw. der Verletzung des rechtlichen Gehörs als unbegründet.
2.4.5. Die Familiennachzugsbestimmungen gemäss Art. 42 bzw. 49 AuG sind wie erwähnt nicht dazu bestimmt, dass jeder Ehepartner auf seiner Seite je für sich unabhängig leben kann bzw. das Getrenntleben ohne wichtigen Grund zum Regelfall wird. Vielmehr sind sie darauf ausgerichtet, dass die Eheleute grundsätzlich zusammenwohnen und die eheliche Gemeinschaft auch tatsächlich anhaltend und nicht bloss sporadisch während kurzer Zeit leben. Insofern hat die Vorinstanz unter Bezugnahme auf die soeben erwähnten Bestimmungen zu Recht die Erteilung der Niederlassungsbewilligung verweigert (vgl. auch Urteil 2C_231/2011 vom 21. Juli 2011 E. 4.5 mit Hinweis).
3.
3.1. Damit bleibt noch zu prüfen, ob dem Eventualantrag des Beschwerdeführers auf Erteilung einer Jahresaufenthaltsbewilligung gestützt auf Art. 50 Abs. 1 lit. a AuG zu entsprechen ist. Gemäss dieser Bestimmung besteht nach Auflösung der Ehe oder der Familiengemeinschaft der Anspruch des Ehegatten auf Erteilung und Verlängerung der Aufenthaltsbewilligung nach Art. 42 AuG weiter, wenn die Ehegemeinschaft mindestens drei Jahre bestanden hat und eine erfolgreiche Integration besteht.
Die Vorinstanz hat die Frage, ob die Ehegemeinschaft mindestens drei Jahre gedauert hat, offen gelassen. Dagegen hat sie die Voraussetzung der erfolgreichen Integration des Beschwerdeführers verneint.
3.2. Eine erfolgreiche Integration liegt praxisgemäss dann vor, wenn der Ausländer namentlich die rechtsstaatliche Ordnung und die Werte der Bundesverfassung respektiert und den Willen zur Teilnahme am Wirtschaftsleben und zum Erwerb der am Wohnort gesprochenen Landessprache bekundet (<ref-law>). Nach Art. 4 der Verordnung über die Integration von Ausländerinnen und Ausländern vom 24. Oktober 2007 (VIntA; SR 142.205) zeigt sich der Beitrag der Ausländerinnen und Ausländer zu ihrer Integration namentlich in der Respektierung der rechtsstaatlichen Ordnung und der Werte der Bundesverfassung (lit. a), im Erlernen der am Wohnort gesprochenen Landessprache (lit. b), in der Auseinandersetzung mit den Lebensbedingungen in der Schweiz (lit. c) und im Willen zur Teilnahme am Wirtschaftsleben und zum Erwerb von Bildung (lit. d). Bei der Prüfung der Integrationskriterien verfügen die zuständigen Behörden über einen grossen Ermessensspielraum, in welchen das Bundesgericht nur zurückhaltend eingreift (vgl. Art. 54 Abs. 2 und 96 Abs. 1 AuG; Urteile 2C_329/2013 vom 27. November 2013 E. 2.1; 2C_930/2012 vom 10. Januar 2013 E. 3.1). Bei einem Ausländer, der in der Schweiz beruflich integriert ist und eine feste Anstellung hat, immer finanziell unabhängig war, sich korrekt verhält und die örtliche Sprache beherrscht, bedarf es ernsthafter besonderer Umstände, um eine erfolgreiche Integration zu verneinen (Urteile 2C_930/2012 vom 10. Januar 2013 E. 3.1, 2C_749/2011 vom 20. Januar 2012 E. 3.3; 2C_839/2010 vom 25. Februar 2011 E. 7.1.2). Nicht erforderlich ist eine besonders qualifizierte berufliche Karriere (Urteil 2C_430/2011 vom 11. Oktober 2011 E. 4.2). Auch das Fehlen besonders enger sozialer Beziehungen schliesst für sich allein eine erfolgreiche Integration nicht aus (Urteil 2C_839/2010 vom 25. Februar 2011 E. 7.1.2). Keine erfolgreiche Integration liegt vor, wenn eine Person kein Erwerbseinkommen erwirtschaften kann, welches ihren Konsum zu decken vermag, und während einer substantiellen Zeitdauer von Sozialleistungen abhängig ist (Urteile 2C_857/2010 vom 22. August 2011 E. 2.3.1; 2C_546/2010 vom 30. November 2010 E. 5.2.3 f.). Umgekehrt ergibt sich aus dem Umstand, dass die ausländische Person sich strafrechtlich nichts zuschulden hat kommen lassen und ihr Unterhalt ohne Sozialhilfe gewährleistet erscheint, für sich allein noch keine erfolgreiche Integration (Urteil 2C_830/2010 vom 10. Juni 2011 E. 2.2.2).
3.3. Die Vorinstanz hat dazu festgestellt, der Beschwerdeführer habe für das Jahr 2007 eine Arbeitsbestätigung des Zirkus D._ sowie ein Arbeitszeugnis von G._ für den Zeitraum April bis September 2009 vorgelegt. Weiter sei er im Juli/August 2010 für einige wenige Einzeltage von einem Personalvermittlungsbüro zur Arbeitsleistung vermittelt worden. Seit Dezember 2010 sei der Beschwerdeführer arbeitslos gemeldet und inzwischen ausgesteuert. Von Mai bis August 2011 sei er in einem Einsatzprogramm beschäftigt gewesen. Trotz dem Umstand, dass er vom 21. Mai 2013 bis zum 20. Februar 2014 in einem befristeten Arbeitsverhältnis bei der E._ AG in Zürich angestellt war, verneinte die Vorinstanz insgesamt eine wirtschaftliche Integration des Beschwerdeführers (vgl. angefochtener Entscheid E. 4e und f).
3.4. Der Beschwerdeführer rügt, die Vorinstanz habe bei der Prüfung seiner beruflichen bzw. wirtschaftlichen Integration nur einen "Bruchteil" der nachgewiesenen und entsprechend aktenkundigen Arbeitstätigkeiten berücksichtigt. Insbesondere habe die Vorinstanz im Wesentlichen folgende Arbeitstätigkeiten unberücksichtigt gelassen: Anstellung als Trommellehrer bei der H._ von Februar 2008 bis Mai 2012 (flexibles Teilzeitarbeitsverhältnis), freiberufliche Tätigkeit als Trommellehrer seit 2005, Anstellung bei der F._ AG von Juni 2008 bis März 2009, Anstellung bei Papierfabrik C._ über ein Vermittlungsbüro, Beschäftigung beim Verein J._ als Perkussionist und als Trommler beim Verein I._ sowie Mitgliedschaft und Tätigkeit bei der Musikgruppe K._.
Entgegen der Auffassung des Beschwerdeführers, vermögen diese Tätigkeiten, die im vorinstanzlichen Entscheid zwar nicht namentlich erwähnt, aber doch in die Gesamtbeurteilung eingeflossen sind, an der mangelnden beruflichen Integration des Beschwerdeführers nichts zu ändern. Es handelt sich bei all diesen Tätigkeiten um temporäre bzw. befristete (Teilzeit-) Einsätze, die teilweise auch im familiären oder befreundeten Umfeld (diverse Musikgruppen) anzusiedeln sind und damit Freizeitcharakter aufweisen. Zwar ist nicht zu übersehen, dass der Beschwerdeführer gewisse Arbeitsbemühungen belegen kann. Insgesamt hat aber die Vorinstanz zu Recht festgestellt, dass der Beschwerdeführer seit 2010 bis April 2013 und wieder ab 20. Februar 2014 über keine feste Anstellung verfügte und damit nicht als beruflich integriert gelten kann. Damit erweist sich auch die Rüge der unvollständigen Sachverhaltsermittlung bzw. der Verletzung des rechtlichen Gehörs als unzutreffend. Der Beschwerdeführer übersieht hier insbesondere, dass ein Gericht nicht auf jedes einzelne Argument eingehen muss, sondern sich bei der Begründung auf die für den Entscheid wesentlichen Punkte beschränken kann (<ref-ruling> E. 5.2 S. 236; <ref-ruling> E. 5.1 S. 237; je mit Hinweisen).
3.5. Daraus ergibt sich, dass die rechtlichen Schlussfolgerungen, die die Vorinstanz aus ihren Sachverhaltsfeststellungen gezogen hat, insgesamt nicht zu beanstanden sind: Zwar hatte der Beschwerdeführer von Zeit zu Zeit Arbeit, aber nie eine feste Anstellung über einen längeren Zeitraum, die ihm ein ausreichendes Einkommen verschafft hätte. Zudem handelte es sich bei seinen Arbeitseinsätzen eher um Aushilfstätigkeiten; seine berufliche Integration - über Festanstellungen - ist ihm offensichtlich nicht gelungen, auch wenn er nie Sozialhilfe beziehen musste (vgl. Urteil 2C_329/2013 vom 27. November 2013 E. 2.4).
3.6. Unter diesen Umständen und insbesondere unter Berücksichtigung der Praxis, dass das Bundesgericht bei der Prüfung der Integrationskriterien nur zurückhaltend eingreift (vgl. E. 3.2 hiervor), genügen die Hinweise auf eine gelungene sprachliche und allenfalls auch soziale Integration, welche die Vorinstanz im Übrigen nicht übersehen hat, nicht für die Annahme einer "erfolgreichen Integration" im Sinne von Art. 50 Abs. 1 lit. a AuG. Die Vorinstanz hat eine erfolgreiche Integration zu Recht verneint, weshalb auch weiterhin offenbleiben kann, wie lange (weniger oder mehr als drei Jahre) der Beschwerdeführer in ehelicher Gemeinschaft mit seiner Ehefrau gelebt hat.
4.
Schliesslich wird weder vorgebracht noch ist ersichtlich, inwiefern der angefochtene Entscheid bzw. die Wegweisung unverhältnismässig sein soll (vgl. angefochtener Entscheid E. 5). Die Vorinstanz hat dazu ausgeführt, in seiner Heimat lebe der Sohn des Beschwerdeführers, seine Mutter sowie die Kindsmutter des Sohnes. Der Schluss der Vorinstanz, damit befinde sich sein engstes und emotional intensivstes Lebensumfeld in seiner Heimat, weshalb seine Wegweisung zumutbar erscheine, wird vor Bundesgericht nicht (mehr) bestritten und scheint nicht unhaltbar.
5.
Daraus ergibt sich, dass die Beschwerde in öffentlich-rechtlichen Angelegenheiten abzuweisen ist.
Damit wird die Beschwerdeführer an sich kostenpflichtig (<ref-law>). Da die Beschwerde aber nicht als aussichtslos zu bezeichnen ist und die Bedürftigkeit des Beschwerdeführer als erstellt gelten kann, was das Verwaltungsgericht auch für das vorinstanzliche Verfahren festgestellt hat, ist dem Gesuch um Gewährung der unentgeltlichen Rechtspflege unter Beiordnung des beigezogenen Rechtsanwalts zu entsprechen (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde in öffentlich-rechtlichen Angelegenheiten wird abgewiesen, soweit darauf einzutreten ist.
2.
Dem Beschwerdeführer wird für das Verfahren vor Bundesgericht die unentgeltliche Rechtspflege gewährt.
2.1. Es werden keine Gerichtskosten erhoben.
2.2. Rechtsanwalt Thomas Häusermann, Zürich, wird zum unentgeltlichen Rechtsbeistand bestellt und aus der Bundesgerichtskasse mit Fr. 2'000.-- entschädigt.
3.
Dieses Urteil wird den Verfahrensbeteiligten, dem Verwaltungsgericht des Kantons Graubünden, 1. Kammer, und dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 4. Dezember 2014
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Zünd
Der Gerichtsschreiber: Winiger