Sachverhalt:
A.
A.a. Der mazedonische Staatsangehörige A._ (geb. 1984) reiste am 8. Januar 2006 in die Schweiz ein. Er ersuchte erfolglos um Asyl und hielt sich nach Abweisung seines Gesuchs illegal in der Schweiz auf. Am 20. April 2011 heiratete er die Schweizer Staatsangehörige B._ (geb. 1988) und erhielt in der Folge eine Aufenthaltsbewilligung zum Verbleib bei seiner Ehefrau. Die Eheleute haben vier gemeinsame Kinder (geb. 2010, 2011, 2012 und 2014), die alle die Schweizer Staatsbürgerschaft besitzen.
A.b. Aufgrund verschiedener strafrechtlicher Verurteilungen verwarnte das Amt für Migration des Kantons Basel-Landschaft A._ am 19. März 2012 erstmals. Am 11. Juli 2013 sprach das Amt für Migration eine zweite Verwarnung aus und verwies u.a. auf offene Verlustscheine in der Höhe von Fr. 17'180.-- und die sozialhilferechtliche Unterstützung der Familie von A._ (rund Fr. 111'600.--). Bis zum 31. Juli 2014 erhöhte sich die bezogene Sozialhilfe auf den Betrag von rund Fr. 156'720.--.
B.
Mit Verfügung vom 11. Juni 2015 lehnte das Amt für Migration die Verlängerung der Aufenthaltsbewilligung von A._ ab und wies diesen aus der Schweiz weg. Als Begründung führte das Amt für Migration die erhebliche Unterstützung durch die Sozialhilfe, die Schuldensituation sowie sein Legalverhalten an.
Der Regierungsrat des Kantons Basel-Landschaft (Beschluss vom 22. Dezember 2015) und das Kantonsgericht Basel-Landschaft (Urteil vom 19. Oktober 2016) wiesen die gegen die Verfügung vom 11. Juni 2015 erhobenen Rechtsmittel ab.
C.
Mit Eingabe vom 24. Februar 2017 erhebt A._ Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht. Er beantragt, das angefochtene Urteil des Kantonsgerichts vom 19. Oktober 2016 sei aufzuheben und dem Beschwerdeführer die Aufenthaltsbewilligung zu verlängern. Eventualiter sei der Beschwerdeführer letztmals zu verwarnen. Weiter ersucht er um Gewährung der unentgeltlichen Rechtspflege.
Der Regierungsrat des Kantons Basel-Landschaft schliesst auf Abweisung der Beschwerde. Das Kantonsgericht Basel-Landschaft und das Staatssekretariat für Migration verzichten auf eine Vernehmlassung.

Erwägungen:
1.
1.1. Gemäss <ref-law> ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten unzulässig gegen Entscheide auf dem Gebiet des Ausländerrechts betreffend Bewilligungen, auf die weder das Bundesrecht noch das Völkerrecht einen Anspruch einräumt. Der Beschwerdeführer beruft sich auf eine bestehende Ehe mit seiner Schweizer Ehefrau sowie die Beziehung zu seinen Schweizer Kindern. Er macht in vertretbarer Weise einen Bewilligungsanspruch nach Art. 42 AuG und Art. 8 EMRK bzw. <ref-law> geltend. Auf die form- und fristgerecht erhobene Eingabe, die sich gegen einen letztinstanzlichen kantonalen Endentscheid richtet, ist einzutreten (vgl. Art. 100 Abs. 1, Art. 42 Abs. 2 sowie Art. 86 Abs. 1 lit. d und Abs. 2 BGG).
1.2. Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten kann eine Rechtsverletzung nach Art. 95 und Art. 96 BGG gerügt werden. 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 (<ref-ruling> E. 3 S. 415). In Bezug auf die Verletzung von Grundrechten gilt eine qualifizierte Rüge- und Substanziierungspflicht (<ref-law>; <ref-ruling> E. 2.2 S. 232; <ref-ruling> E. 2.5 S. 314).
1.3. Das Bundesgericht legt seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (<ref-law>). Es kann die Sachverhaltsfeststellung der Vorinstanz von Amtes wegen berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinn von <ref-law> beruht (<ref-law>). Die beschwerdeführende Partei kann die Feststellung des Sachverhalts unter den gleichen Voraussetzungen beanstanden, wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>).
1.4. Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>). Es ist somit weder an die in der Beschwerde geltend gemachten Argumente noch an die Erwägungen der Vorinstanz gebunden; es kann eine Beschwerde aus einem anderen als dem angerufenen Grund gutheissen oder eine Beschwerde mit einer von der Argumentation der Vorinstanz abweichenden Begründung abweisen.
1.5. Neue Tatsachen und Beweismittel dürfen nur so weit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt ("unechte" Noven gemäss <ref-law>). Echte Noven, d.h. Tatsachen, die erst nach dem angefochtenen Urteil eingetreten sind, bleiben im bundesgerichtlichen Verfahren in jedem Fall unberücksichtigt (<ref-ruling> E. 3.1.2 S. 123; <ref-ruling> E. 5.2.4 S. 229; <ref-ruling> E. 2.1 S. 343 f.). Der vom Beschwerdeführer eingereichte Arbeitsvertrag vom 15. März 2017 zwischen ihm und der F._ GmbH ist somit als echtes Novum unzulässig und im vorliegenden Verfahren nicht weiter zu beachten. Das gleiche gilt für den vom Amt für Migration eingereichten Strafbefehl der Staatsanwaltschaft Solothurn vom 24. Mai 2017, den Aktenbericht der KESB U._ vom 21. Juni 2017, wonach der Beschwerdeführer bald aus der Familienwohnung ausziehen werde, bzw. den Beschluss der KESB U._ vom 31. Juli 2017 betreffend die Fremdplatzierung von zwei Kindern des Beschwerdeführers.
2.
2.1. Der ausländische Ehegatte einer Schweizerin hat nach Art. 42 Abs. 1 AuG Anspruch auf Erteilung und Verlängerung der Aufenthaltsbewilligung, wenn er mit dieser zusammen wohnt. Dabei liegt eine (relevante) Ehegemeinschaft nur dann vor, wenn die eheliche Beziehung tatsächlich gelebt wird und ein gegenseitiger Ehewille besteht, was die Vorinstanz im vorliegenden Fall bejaht hat. Nach einem ordnungsgemässen und ununterbrochenen Aufenthalt von fünf Jahren hat der Ehegatte Anspruch auf Erteilung der Niederlassungsbewilligung (Art. 42 Abs. 3 AuG). Allerdings erlischt der Anspruch nach Art. 42 AuG unter anderem, wenn Widerrufsgründe nach Art. 63 AuG vorliegen (Art. 51 Abs. 1 lit. b AuG).
2.2. Die Vorinstanz hat ausgeführt, der Widerrufsgrund von Art. 62 Abs. 1 lit. b AuG sei nicht erfüllt (vgl. angefochtener Entscheid E. 6.3). Dagegen hat sie den Widerrufsgrund von Art. 62 Abs. 1 lit. c AuG (vgl. angefochtener Entscheid E. 6.4 bis 6.7) bzw. Art. 62 Abs. 1 lit. e AuG (vgl. angefochtener Entscheid E. 7) bejaht. Der Beschwerdeführer macht im Wesentlichen geltend, die Widerrufsgründe von Art. 62 Abs. 1 lit. c bzw. lit. e AuG seien nicht erfüllt.
2.3. Entgegen der Ansicht der Vorinstanz - wie auch des Beschwerdeführers - ist indes im vorliegenden Fall nicht zu prüfen, ob ein Widerrufsgrund nach Art. 62 AuG vorliegt. Vielmehr stellt sich die Frage, ob die Voraussetzungen des Widerrufsgrundes von Art. 63 AuG, im Besonderen Art. 63 Abs. 1 lit. c AuG, erfüllt sind oder nicht (vgl. E. 2.1 hiervor).
Art. 63 Abs. 1 lit. c AuG sieht vor, dass die zuständige Behörde die Niederlassungsbewilligung widerrufen kann, wenn die ausländische Person oder eine Person, für die sie zu sorgen hat, dauerhaft und in erheblichem Mass auf Sozialhilfe angewiesen ist.
3.
3.1. Die Vorinstanz hat hier verbindlich festgestellt, dass der Beschwerdeführer seit seiner Einreise 2006 insgesamt zwölfmal verurteilt worden ist (bedingte Gefängnisstrafe von fünf Tagen, total 239 Tagessätze Geldstrafe sowie Bussen in der Höhe von total Fr. 4'400.--). Zudem weist der Beschwerdeführer öffentlich- und privatrechtliche Schulden in beträchtlicher Höhe vor: Gemäss Betreibungsregisterauszug vom 10. Dezember 2015 sind auf seinem Namen in den letzten fünf Jahren 36 Betreibungen in einem Gesamtbetrag von Fr. 56'247.60 und 26 Verlustscheine von insgesamt Fr. 45'466.45 verzeichnet.
3.2. Ob damit bereits der Widerrufsgrund gestützt auf Art. 63 Abs. 1 lit. b AuG (schwerwiegender Verstoss gegen öffentliche Sicherheit und Ordnung) gesetzt worden ist, kann hier offen gelassen werden, da der Widerrufsgrund von Art. 63 Abs. 1 lit. c AuG (dauerhafte und erhebliche Sozialhilfeabhängigkeit) - wie nachfolgend aufgezeigt wird - ohnehin zu bejahen ist.
3.3. Praxisgemäss ist der Widerrufsgrund nach Art. 63 Abs. 1 lit. c AuG erfüllt, wenn konkret die Gefahr einer fortgesetzten und erheblichen Fürsorgeabhängigkeit besteht. Blosse finanzielle Bedenken genügen nicht. Neben den bisherigen und den aktuellen Verhältnissen ist auch die wahrscheinliche finanzielle Entwicklung auf längere Sicht abzuwägen. Ein Widerruf soll in Betracht kommen, wenn eine Person hohe finanzielle Unterstützungsleistungen erhalten hat und nicht damit gerechnet werden kann, dass sie in Zukunft für ihren Lebensunterhalt sorgen wird (Urteil 2C_1058/2013 vom 11. September 2014 E. 2.3 mit Hinweisen).
3.4. Die Vorinstanz hat verbindlich festgestellt, der Beschwerdeführer verfüge zum Zeitpunkt des angefochtenen Entscheids über keine Arbeitsstelle und habe auch keine Nachweise für allfällige Arbeitsbemühungen erbracht. In den letzten fünf Jahren sind für den Beschwerdeführer und seine Familie Sozialhilfekosten in der Höhe von über Fr. 345'000.-- entstanden (gemäss den vorinstanzlichen Feststellungen ohne die zusätzlichen Kosten für die Heimunterbringung der drei Söhne und deren Beistand), was im Sinne der Rechtsprechung im Rahmen von Art. 63 Abs. 1 lit. c AuG als erheblich erscheint (Urteile 2C_120/2015 vom 2. Februar 2016 E. 2.2; 2C_1058/2013 vom 11. September 2014 E. 2.4; 2C_268/2011 vom 22. Juli 2011 E. 6.2.4). Gleichzeitig ist der Beschwerdeführer auch den Auflagen gemäss der Verwarnung vom 11. Juli 2013 nicht nachgekommen (aktive Bemühung um Entlassung aus der Sozialhilfe). Soweit der Beschwerdeführer ausführt, es sei ihm nun endlich gelungen, eine Arbeitsstelle zu finden, kann darauf nicht eingegangen werden (Novenverbot; vgl. E. 1.5 hiervor). Entgegen seiner Ansicht trifft es sodann nicht zu, dass er sich stets bemüht haben soll, eine Arbeitsstelle zu finden. Vielmehr hat er sogar im August 2016 eine mögliche Anstellung bei der G._ AG aus nicht näher bekannten Gründen nicht angenommen.
3.5. Die Vorinstanz ist damit im Ergebnis zu Recht davon ausgegangen, dass der Widerrufsgrund der Sozialhilfeabhängigkeit nach Art. 63 Abs. 1 lit. c AuG vorliegend erfüllt ist (vgl. auch E. 1.4 hiervor).
Daraus ergibt sich, dass das öffentliche Interesse an einer Beendigung des Aufenthalts des Beschwerdeführers in der Schweiz insgesamt als erheblich zu bezeichnen ist.
4.
4.1. Sind Widerrufsgründe gegeben, so ist der Widerruf der Bewilligung nur dann rechtens, wenn die jeweils im Einzelfall vorzunehmende Interessenabwägung diese Massnahme als verhältnismässig erscheinen lässt, wobei einerseits die - bereits dargelegten - öffentlichen Interessen, andererseits die persönlichen Verhältnisse und der Grad der Integration der ausländischen Person zu berücksichtigen sind (vgl. Art. 96 AuG).
4.2. Der Beschwerdeführer ist mit einer Schweizerin verheiratet und Vater von vier minderjährigen Kindern schweizerischer Nationalität, mit denen er gemäss eigenen Angaben zusammen lebt. Die Notwendigkeit einer Interessenabwägung ergibt sich somit auch aus Art. 13 Abs. 1 i.V.m. Art. 36 Abs. 2 und 3 BV sowie Art. 8 EMRK. Gemäss Art. 8 Ziff. 2 EMRK ist ein Eingriff in das Recht auf Achtung des Familienlebens statthaft, wenn er gesetzlich vorgesehen ist und in einer demokratischen Gesellschaft für die nationale oder öffentliche Sicherheit, für das wirtschaftliche Wohl des Landes, zur Aufrechterhaltung der Ordnung, zur Verhütung von Straftaten, zum Schutz der Gesundheit oder der Moral oder zum Schutz der Rechte und Freiheiten anderer notwendig ist. Die Konvention verlangt demnach ebenfalls eine Abwägung der sich gegenüberstehenden privaten Interessen an der Weitergeltung der Bewilligung und den öffentlichen Interessen an deren Widerruf, wobei Letztere in dem Sinn überwiegen müssen, dass sich der Eingriff als notwendig erweist (<ref-ruling> E. 2.2 S. 147 f.; <ref-ruling> E. 2.2.1 S. 156; <ref-ruling> E. 2.1 S. 147; <ref-ruling> E. 2 S. 6 mit Hinweisen).
4.3. Bei der Interessenabwägung sind namentlich die Schwere eines allenfalls begangenen Delikts, der seit der Tat vergangene Zeitraum, das Verhalten des Ausländers während dieser Periode, die Auswirkungen auf die primär betroffene Person sowie deren familiäre Situation zu berücksichtigen. Zudem sind die Dauer der ehelichen Beziehung und weitere Gesichtspunkte relevant, welche Rückschlüsse auf deren Intensität zulassen (wie etwa die Geburt und das Alter allfälliger Kinder). Von Bedeutung sind auch die Nachteile, welche dem Ehepartner oder den Kindern erwachsen würden, müssten sie dem Betroffenen in dessen Heimat folgen (zum Ganzen <ref-ruling> E. 4.3 S. 381 f.; Urteil 2C_679/2011 vom 21. Februar 2012 E. 3.2 mit weiteren Hinweisen). Zu beachten ist auch die Qualität der sozialen, kulturellen und familiären Beziehungen zum Gast- bzw. zum Heimatland (Urteil 2C_711/2011 vom 27. März 2012 E. 4.2 mit Hinweisen; siehe zum Ganzen auch Urteil des EGMR Boultif gegen Schweiz vom 2. August 2001 [Nr. 54273/00]). Bei der Abwägung ist insbesondere auch das Kindeswohl angemessen zu berücksichtigen (vgl. Urteil 2C_1125/2014 vom 9. September 2015 E. 4.2).
4.4. Die Vorinstanz hat im angefochtenen Entscheid - wie der Beschwerdeführer an sich zu Recht vorbringt - eine etwas rudimentäre Interessenabwägung vorgenommen. So hat sie ausgeführt, der Beschwerdeführer sei in Anbetracht seines langjährigen Aufenthalts in der Schweiz wirtschaftlich schlecht integriert. Die soziale Integration sei teilweise vorhanden, da er zur Zeit mit seiner Familie zusammen lebe und ein Teil seiner Verwandtschaft (sein Bruder, seine Tante, sein Cousin und drei Cousinen, jeweils mit Familie) in der Schweiz wohne. Da aber ein Teil seiner Familie (seine Eltern und drei Schwestern) in Mazedonien lebten, verfüge er in seiner Heimat über ein soziales Netz. Den Kontakt zu seinen Kindern und seiner Ehefrau könne er auch aus Mazedonien aufrecht erhalten, sei dies durch regelmässige Kurz- oder Ferienaufenthalte oder mittels moderner Kommunikationsmittel. Auch wenn eine Rückkehr des Beschwerdeführers nach Mazedonien diesen und dessen Familie zweifellos hart treffen würde, ergebe sich daraus kein Hindernis für eine Wegweisung (vgl. angefochtener Entscheid E. 8.4). Dagegen fehlt im angefochtenen Entscheid eine vertiefte Auseinandersetzung mit den Folgen, welche eine Wegweisung unter den erwähnten Umständen für die Ehefrau und insbesondere die Kinder des Beschwerdeführers hätte.
4.5.
4.5.1. Vor der Vorinstanz hatte der Beschwerdeführer diesbezüglich geltend gemacht, er führe ein intaktes Familienleben und er wolle sich fortan für seine Familie einsetzen und die Kinder gemeinsam mit seiner Ehefrau aufziehen. Die Ehefrau hatte ausgeführt, sie blicke ihrer Zukunft mit ihrem Ehemann und ihren Kindern positiv entgegen und das Verhältnis des Ehemannes zu seinen Kindern sei gut. Auch vor Bundesgericht macht der Beschwerdeführer geltend, es bestehe eine "intakte und intensiv gelebte Beziehung" zu seinen Kindern; er betreue die Kinder und unternehme viel mit ihnen.
4.5.2. Aus den Akten ergibt sich indes ein anderes Bild: So lässt sich dem Beschluss des Regierungsrates des Kantons Basel-Landschaft vom 22. Dezember 2015 entnehmen, dass im März 2014 drei Kinder (C._ [geb. 2010], D._ [geb. 2011] und E._ [geb. 2012]) durch die zuständige KESB fremd platziert worden sind. Das Kantonsgericht Basel-Landschaft, Abteilung Verfassungs- und Verwaltungsrecht, hat mit Urteil vom 13. August 2014 den Obhutsentzug bis längstens Ende Januar 2015 befristet. Das Kantonsgericht hat dabei unter anderem ausgeführt, die Eltern würden "faktisch getrennt" wohnen. Die Beziehung des Beschwerdeführers zu seinen Kindern sei angespannt gewesen und er habe die Kinder vernachlässigt. Die erwähnten Spannungen könnten gemäss Kantonsgericht zu einer Gefährdung des Kindeswohls führen (E. 4.3 und 4.4 des erwähnten Urteils des Kantonsgerichts vom 13. August 2014). In Bezug auf den ältesten Sohn C._ hat die zuständige KESB mit Beschluss vom 3. Juni 2015 den Entzug des Aufenthaltsrechts zwar aufgehoben, aber gleichzeitig eine Erziehungsbeistandschaft angeordnet. Weiter lässt sich dem Beschluss des Regierungsrates des Kantons Basel-Landschaft vom 22. Dezember 2015 entnehmen, dass der Beschwerdeführer im Zeitraum Dezember 2015 nur selten bei seiner Familie anzutreffen war und er sich kaum an der Betreuung der Kinder oder an der Hausarbeit beteiligt habe.
4.5.3. In Ergänzung des insoweit unvollständig und damit bundesrechtswidrig festgestellten Sachverhalts (<ref-law>; <ref-ruling> E. 3.1 S. 373; <ref-ruling> E. 3.4.2 S. 295) ist mithin davon auszugehen, dass sich das Familienleben des Beschwerdeführers nicht als dermassen intakt erweist, wie er dies in seiner Beschwerdeschrift dargelegt hat. Die Intensität der Beziehungen zu seiner Ehefrau bzw. zu seinen Kindern ist damit offensichtlich zu relativieren. Unter diesen Umständen ist der Schluss der Vorinstanz, wonach eine Rückkehr des Beschwerdeführers nach Mazedonien diesen und dessen Familie zwar hart treffen, sich daraus indes kein Hindernis für eine Wegweisung ergeben würde (vgl. E. 4.4 hiervor), im Ergebnis nicht zu beanstanden.
4.5.4. Weiter ist zwar ebenfalls das Kindeswohl zu berücksichtigen, wie der Beschwerdeführer sinngemäss geltend macht (vgl. Art. 3 des Übereinkommens vom 20. November 1989 über die Rechte des Kindes [UNO-KRK; SR 0.107]). Über Art. 8 EMRK und <ref-law> hinausgehende Ansprüche auf Bewilligung ergeben sich aus der UNO-KRK vorliegend jedoch nicht (vgl. BGE <ref-ruling> E. 2.2.2 S. 156 f.; <ref-ruling> E. 3b S. 367 f.; Urteil 2C_956/2012 vom 22. Februar 2013 E. 3.4.3 mit Hinweisen).
4.5.5. Unbehelflich ist schliesslich auch der Verweis des Beschwerdeführers auf das Urteil des EGMR i.S. Udeh gegen Schweiz vom 16. April 2013: Dieser Entscheid ist kein Grundsatzentscheid. Vielmehr hat der EGMR dort ausschliesslich die Umstände des konkreten Einzelfalls berücksichtigt, die teilweise erst nach der Beurteilung durch das Bundesgericht eingetreten und nicht in jeder Hinsicht mit der vorliegenden Angelegenheit vergleichbar sind (vgl. <ref-ruling> E. 2.4 S. 327 ff.). So war im Urteil des EGMR u.a. entscheidend, dass Udeh in der Schweiz zwei schulpflichtige Kinder hatte, zu welchen er eine intakte Beziehung unterhielt.
4.6. Zusammengefasst ergibt sich, dass die privaten Interessen des Beschwerdeführers am Verbleib in der Schweiz zwar insgesamt bedeutend sind, diese aber die erheblichen öffentlichen Interessen an einer Fernhaltung des Beschwerdeführers (vgl. E. 3.5 hiervor) nicht zu überwiegen vermögen. Der angefochtene Entscheid verletzt damit weder Bundes- noch Konventionsrecht.
5.
Daraus ergibt sich, dass die Beschwerde in öffentlich-rechtlichen Angelegenheiten abzuweisen ist.
Damit wird der Beschwerdeführer an sich kostenpflichtig (<ref-law>). Da die Beschwerde aber nicht gerade als von vornherein aussichtslos zu bezeichnen ist und die Bedürftigkeit des Beschwerdeführers als erstellt gelten kann, was das Kantonsgericht auch für das vorinstanzliche Verfahren und der Regierungsrat für das Beschwerdeverfahren vor dem Regierungsrat angenommen hat, ist dem Gesuch um Gewährung der unentgeltlichen Rechtspflege unter Beiordnung des beigezogenen Rechtsanwalts zu entsprechen (<ref-law>).

Das Bundesgericht erkennt:
1.
Die Beschwerde in öffentlich-rechtlichen Angelegenheiten wird abgewiesen.
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 Krishna Müller, Bern, wird zum unentgeltlichen Rechtsbeistand bestellt und aus der Bundesgerichtskasse mit Fr. 2'000.-- entschädigt.
3.
Dieses Urteil wird den Verfahrensbeteiligten, dem Kantonsgericht Basel-Landschaft, Abteilung Verfassungs- und Verwaltungsrecht, und dem Staatssekretariat für Migration schriftlich mitgeteilt.
Lausanne, 2. November 2017
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Seiler
Der Gerichtsschreiber: Winiger