Fatti: A. Il cittadino guineano A._ è giunto in Svizzera nel giugno 2004. Il mese successivo ha ottenuto un permesso di dimora UE/AELS, rinnovato un'ultima volta fino al 2 giugno 2014, per vivere con la moglie B._, cittadina portoghese titolare di un'autorizzazione di domicilio UE/AELS. La coppia, sposata dal dicembre 2002, ha avuto due figli: C._ e D._, cittadini portoghesi. Dopo una prima separazione, il 1° agosto 2013 i coniugi hanno cessato definitivamente la comunione domestica. Con sentenza del 3 ottobre 2014, il Giudice civile competente ha pronunciato il divorzio, affidando i figli alla madre, concedendo al padre un ampio diritto di visita, e imponendo a quest'ultimo il versamento di un contributo mensile di fr. 1'300.--. L'autorità parentale è rimasta congiunta. B. Nel corso del suo soggiorno in Svizzera, A._ ha interessato le autorità amministrative e penali nei seguenti termini (elenco ripreso dal giudizio impugnato) : 13.06.06: sentenza Juges d'instruction Genève per delitto contro la LStup (09.06.06) : pena detentiva di 4 mesi. Liberato condizionalmente il 7.09.06 con un periodo di prova di 1 anno; 30.05.07: DA per delitto contro la LStup (29.03- 30.03.07) : pena detentiva di 2 mesi; 23.08.07: sentenza Juges d'instruction Genève per delitto contro la LStup (22-23.08.07), violenza o minaccia contro le autorità e i funzionari (22-23.08.07) : pena detentiva di 3 mesi; 19.07.10: DA per ripetuta guida in stato di inattitudine (18.08.06 e 14.11.09: concentrazione qualificata nel sangue: min. 0.96-max. 1.21 g o/oo, rispettivamente min. 0.84-max. 1.24 g o/oo) : pena pecuniaria di 30 aliquote giornaliere da fr. 80.--, sospesa condizionalmente con un periodo di prova di 3 anni, e multa di fr. 1'000.--; 18.11.11: ammonito dal Dipartimento, con l'avvertenza che in caso di recidiva o di comportamento scorretto, sarebbe stata presa in esame la possibilità di adottare adeguate misure amministrative nei suoi confronti; 26.03.12: DA per lesioni semplici (25.07.10) : pena pecuniaria di 20 aliquote giornaliere da fr. 30.--, non revoca del beneficio della sospensione condizionale della pena pecuniaria di cui al DA 19.07.10, ma prolungamento del periodo di prova di 1 anno; 08.07.14: sentenza Strafgericht del Canton Basilea-Città per infrazione aggravata alla LStup (08.01.12) : condanna alla pena detentiva di 24 mesi, sospesi condizionalmente per un periodo di prova di 3 anni, e non revoca del beneficio della sospensione condizionale concessa alla pena pecuniaria di cui al DA 19.07.10; 06.05.15: DA per eccesso di velocità (16.12.14) : multa di fr. 40.--; 19.10.16: DA per divieto di posteggio (23.07.16) : multa di fr. 60.--; 21.10.16: DA per contravvenzione alla legge federale sulla circolazione stradale (29.07.16) : multa di fr. 40.--. C. Tenuto conto della sua condotta, l'ufficio competente gli ha negato a due riprese il rilascio di un permesso di domicilio UE/AELS (4 novembre 2009 e 12 maggio 2011). Il 13 novembre 2014, A._ ha notificato la propria partenza alla volta di X._ (SZ), dove si era trasferito il 1° maggio precedente. Nel seguito, le autorità del Canton Svitto hanno tuttavia deciso di non entrare in materia sulla domanda di cambiamento di Cantone rispettivamente di respingerla (decisione del 13 ottobre 2015). Ritornato in Ticino, A._ ha presentato alla Sezione della popolazione del Dipartimento delle istituzioni una richiesta di rilascio di un permesso di domicilio. Il 21 dicembre 2015, quest'ultima l'ha però respinta. Nel contempo, ha deciso che, per ragioni di ordine pubblico, dati non fossero neanche gli estremi per un rinnovo del permesso di dimora di cui A._ aveva beneficiato in precedenza. Su ricorso, il diniego del diritto a rimanere in Svizzera è stato confermato sia dal Consiglio di Stato (28 marzo 2017) che dal Tribunale amministrativo ticinese (25 settembre 2018). Il 2 settembre 2016, quando la procedura era già pendente davanti al Governo ticinese, A._ si è sposato con la cittadina elvetica E._, la quale ha continuato a vivere nel Canton Svitto. D. Il 31 ottobre 2018 A._ ha inoltrato dinanzi al Tribunale federale un ricorso in materia di diritto pubblico, con cui chiede che il giudizio della Corte cantonale e la decisione di prima istanza siano annullate e che gli sia concesso il rinnovo del permesso di dimora, domandando inoltre l'ammissione all'assistenza giudiziaria. Il Tribunale amministrativo si è riconfermato nelle motivazioni e nelle conclusioni della propria sentenza. Ad essa ha fatto in sostanza rinvio anche la Sezione della popolazione. Il Consiglio di Stato si è invece rimesso al giudizio di questa Corte. Con decreto del 6 novembre 2018 è stato concesso l'effetto sospensivo al gravame.