Sachverhalt:
A.
Der deutsche Staatsangehörige A._ zog am 1. Mai 2016 nach Luzern und beantragte am 2. Mai 2016 beim Strassenverkehrsamt Luzern einen schweizerischen Führerausweis. Das Amt verweigerte ihm am 4. August 2016 die Ausstellung eines solchen und erklärte das Recht zur Verwendung des ausländischen nationalen und allenfalls internationalen Führerausweises auf unbestimmte Zeit als aberkannt; einer allfälligen Verwaltungsgerichtsbeschwerde entzog es die aufschiebende Wirkung.
Die von A._ dagegen erhobene Verwaltungsgerichtsbeschwerde wies der Einzelrichter der 4. Abteilung des Kantonsgerichts Luzern mit Urteil vom 23. November 2016 ab.
B.
A._ führt Beschwerde in öffentlich-rechtlichen Angelegenheiten und beantragt die Aufhebung des Urteils des Kantonsgerichts Luzern.
Mit Verfügung vom 5. Januar 2017 hat der Präsident der I. öffentlich-rechtlichen Abteilung das Gesuch von A._ um Gewährung der aufschiebenden Wirkung abgewiesen.
Das Kantonsgericht Luzern und das Bundesamt für Strassen ASTRA beantragen die Abweisung der Beschwerde. Denselben Antrag stellt das Strassenverkehrsamt. In seiner Replik hält A._ an der Beschwerde fest. Nach Ablauf der Beschwerdefrist hat er zudem mehrere Beschwerdeergänzungen eingereicht.

Erwägungen:
1.
1.1. Angefochten ist ein kantonal letztinstanzlicher Entscheid betreffend Administrativmassnahmen im Strassenverkehrsrecht. Da es sich um eine Angelegenheit des öffentlichen Rechts handelt und auch kein Ausnahmegrund nach <ref-law> gegeben ist, steht dagegen die Beschwerde nach <ref-law> offen. Der Beschwerdeführer hat am vorinstanzlichen Verfahren teilgenommen (Art. 89 Abs. 1 Bst. a BGG). Er ist durch den angefochtenen Entscheid besonders berührt und hat ein schutzwürdiges Interesse an dessen Aufhebung oder Änderung (Art. 89 Abs. 1 Bst. b und c BGG). Die übrigen Sachurteilsvoraussetzungen geben zu keinen Bemerkungen Anlass. Auf die Beschwerde ist einzutreten.
1.2. Wie bereits vor der Vorinstanz hat der Beschwerdeführer nach Ablauf der Beschwerdefrist (Art. 100 Abs. 1 und Art. 48 Abs. 1 BGG) dem Bundesgericht zahlreiche Beschwerdeergänzungen eingereicht, in denen er seine Anträge und Begründungen neu darstellt, wiederholt oder variiert, aber auch neue Argumente vorträgt. Diese Eingaben sind verspätet und können nicht berücksichtigt werden.
1.3. In der Beschwerdeschrift ist in gedrängter Form darzulegen, inwiefern der angefochtene Akt Recht verletzt (<ref-law>). Unerlässlich ist, dass die Beschwerde auf die Begründung des angefochtenen Entscheids eingeht und im Einzelnen aufzeigt, worin eine Verletzung von Bundesrecht liegt. Die beschwerdeführende Partei soll in der Beschwerdeschrift nicht bloss die Rechtsstandpunkte, die sie im kantonalen Verfahren eingenommen hat, erneut bekräftigen, sondern mit ihrer Kritik an den als rechtsfehlerhaft erachteten Erwägungen der Vorinstanz ansetzen (<ref-ruling> E. 2 S. 89, 115 E. 2 S. 116). Auf Rügen, mit denen bloss allgemein gehaltene, appellatorische Kritik am angefochtenen Entscheid geübt wird, tritt das Bundesgericht nicht ein (<ref-ruling> E. 1.3 S. 262; <ref-ruling> E. 2.8; <ref-ruling> E. 1.3 S. 60; je mit Hinweisen).
2.
2.1. Mit der Beschwerde kann unter anderem die Verletzung von Bundesrecht und Völkerrecht gerügt werden (Art. 95 lit. a und b BGG). Die Verletzung von Grundrechten prüft das Bundesgericht nur insofern, als eine solche Rüge in der Beschwerde vorgebracht und begründet worden ist (<ref-law>; <ref-ruling> E. 1.6 S. 130). Inwiefern verfassungsmässige Rechte verletzt worden sein sollen, ist in der Beschwerde klar und detailliert anhand der Erwägungen des angefochtenen Entscheids darzulegen (<ref-ruling> E. 1.6 S. 130; <ref-ruling> E. 8 S. 156).
2.2. Soweit der Beschwerdeführer in seinen Beschwerdeergänzungen bloss vorbringt, die "postfaktische Verfügung" des Strassenverkehrsamts verletze seine "Grundrechte", ist darauf nicht einzutreten. Gleiches gilt in Bezug auf sein mehrfaches Vorbringen, die Vorinstanz sei in Willkür verfallen (<ref-law>). Rechtsprechungsgemäss genügt es nicht, wenn er einfach behauptet, der angefochtene Entscheid sei willkürlich (<ref-ruling> E. 3 S. 352; <ref-ruling> E. 5.5 S. 5). Willkür liegt nicht schon dann vor, wenn eine andere Lösung ebenfalls in Betracht zu ziehen oder gar vorzuziehen wäre, sondern nur, wenn der angefochtene Entscheid offensichtlich unhaltbar ist, mit der tatsächlichen Situation in klarem Widerspruch steht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft (<ref-ruling> E. 2.1; <ref-ruling> E. 3.2.5 S. 339). Dass die von der Vorinstanz gezogenen Schlüsse nicht mit der eigenen Darstellung des Beschwerdeführers übereinstimmen, belegt keine Willkür (<ref-ruling> E. 2.3 S. 266 mit Hinweisen). Erforderlich ist zudem, dass der Entscheid nicht nur in der Begründung, sondern auch im Ergebnis willkürlich ist (<ref-ruling> E. 2.1 S. 19 mit Hinweisen), was vom Beschwerdeführer nicht dargetan wird und vorliegend auch nicht ersichtlich ist.
3.
3.1. Das Bundesgericht legt seinem Urteil den Sachverhalt zu Grunde, den die Vorinstanz festgestellt hat (<ref-law>). Die Sachverhaltsfeststellung kann nur gerügt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>).
3.2. Gestützt auf die Akten sowie die Auskünfte der zuständigen deutschen und österreichischen Behörden hat die Vorinstanz festgestellt, dem Beschwerdeführer sei am 17. Januar 1995 erstmalig die Fahrerlaubnis in Deutschland erteilt worden. Wegen Verstössen gegen das Strassenverkehrsgesetz innerhalb der gesetzlichen Probezeit sei ihm in Deutschland die Fahrerlaubnis durch Bescheid vom 30. Dezember 1998 entzogen worden. Nach durchgeführtem Widerspruchsverfahren sei der Entzug am 14. April 1999 in Bestandeskraft erwachsen. Danach sei es dem Beschwerdeführer gelungen, den aberkannten und damit ungültigen deutschen Ausweis am 20. August 1999 in einen österreichischen Führerausweis umzutauschen und diesen am 16. Juli 2003 in einen schweizerischen. Zuletzt sei ihm in Österreich am 13. April 2006 ein Duplikatführerschein ausgestellt worden, da er den schweizerischen Führerschein als gestohlen angezeigt habe. Zusammenfassend ergebe sich, dass der deutsche Führerausweis bereits vor dem ersten Umtausch in den österreichischen Führerausweis am 20. August 1999 entzogen worden sei. Sämtlichen Führerausweisen, die nach dem deutschen Führerausweisentzug ausgestellt worden seien, sei keine gültige originäre Fahrerlaubnis mehr zugrunde gelegen, zumal der Beschwerdeführer nie eine neue Fahrprüfung absolviert, sondern die Ausweise unter Bezugnahme auf Umtausch- und Duplikatspapiere erlangt habe, welche ihrerseits ursprünglich auf dem entzogenen deutschen Führerausweis gegründet hätten. Insoweit habe der Beschwerdeführer seit dem Entzug der deutschen Fahrerlaubnis nicht mehr über eine gültige Fahrberechtigung verfügt, auch wenn die erlangten österreichischen Ausweise und der Schweizer Umtauschausweis Gegenteiliges suggerieren würden.
3.3. Der Beschwerdeführer belässt es dabei, der Vorinstanz vorzuwerfen, diese habe Tatsachen "umgedichtet" und "objektiv unrichtig" darauf abgestellt, dass er nach dem 17. Januar 1995 keine erneute Fahrerlaubnisprüfung absolviert habe und deshalb kein neuer, originär gültiger ausländischer Führerschein mit neuer Fahrberechtigung vorliege. Weshalb die vorinstanzlichen Feststellungen offensichtlich unrichtig sein sollen, wird vom Beschwerdeführer hingegen nicht dargetan und ist nach dem Ausgeführten auch nicht ersichtlich. Damit ist die Sachverhaltsrüge als unbegründet abzuweisen.
4.
4.1. Wer ein Motorfahrzeug führt, bedarf des Führerausweises (<ref-law>). Dieser wird von den kantonalen Verwaltungsbehörden am Wohnsitz des Fahrzeugführers erteilt und entzogen (<ref-law>). Personen aus dem Ausland dürfen in der Schweiz Motorfahrzeuge führen, falls sie einen gültigen nationalen oder internationalen Führerausweis besitzen (Art. 42 Abs. 1 lit. a der Verordnung vom 27. Oktober 1976 über die Zulassung von Personen und Fahrzeugen zum Strassenverkehr [Verkehrszulassungsverordnung, VZV; SR 741.51]).
4.2. Nach Art. 41 Abs. 2 lit. a/i des Übereinkommens über den Strassenverkehr vom 8. November 1968 (SR 0.741.10) anerkennen die Vertragsparteien jeden nationalen Führerschein als gültig, um auf ihrem Gebiet ein Fahrzeug zu führen, vorausgesetzt, dass dieser noch gültig ist und von einer anderen Vertragspartei ausgestellt worden ist. Ausländische Fahrzeugführer, die seit zwölf Monaten in der Schweiz wohnen und sich in dieser Zeit nicht länger als drei Monate ununterbrochen im Ausland aufgehalten haben, benötigen jedoch einen schweizerischen Führerausweis (<ref-law>). Dem Inhaber eines gültigen nationalen ausländischen Ausweises wird der schweizerische Führerausweis der entsprechenden Kategorie erteilt, wenn er auf einer Kontrollfahrt nachweist, dass er die Verkehrsregeln kennt und Fahrzeuge der Kategorien, für die der Ausweis gelten soll, sicher zu führen versteht (<ref-law>; die Kontrollfahrt entfällt, wenn der Ausweis von einem Staat gemäss der Länderliste nach <ref-law> ausgestellt worden ist). Mangels eines gültigen ausländischen Ausweises hat der Bewerber eine Führerprüfung abzulegen (<ref-law>; vgl. das Urteil des Bundesgerichts 1C_441/2012 vom 4. März 2013 E. 2).
4.3. Nach <ref-law> sind Ausweise und Bewilligungen zu entziehen, wenn festgestellt wird, dass die gesetzlichen Voraussetzungen zu deren Erteilung nicht oder nicht mehr bestehen. Ausländische Führerausweise können in der Schweiz nach den gleichen Bestimmungen aberkannt werden, die für den Entzug des schweizerischen Führerausweises gelten (<ref-law>). Hingegen können sie nicht entzogen werden, andernfalls ein unzulässiger Eingriff in ausländische Hoheitsrechte vorliegen würde (<ref-ruling> E. 2.3 S. 178 mit Hinweis). Nach <ref-law> sind Ausweise unter anderem auf unbestimmte Zeit abzuerkennen, wenn sie in Umgehung der schweizerischen oder ausländischen Zuständigkeitsbestimmungen im Ausland erworben worden sind.
4.4. Die Vorinstanz hat den Umgehungstatbestand gemäss <ref-law> nach Massgabe der bundesgerichtlichen Rechtsprechung (Urteil 1C_441/2012 vom 4. März 2013 betreffend einen gefälschten Führerausweis) weit ausgelegt. Dabei ist sie zum Schluss gelangt, als Umgehung im Sinne von <ref-law> müsse schon wegen der Wertungsübereinstimmung miterfasst sein, wenn im Ausland ohne bestehende ursprüngliche Fahrerlaubnis erlangte Umtauschausweise oder Duplikate infrage stünden. Diese Auslegung werde zusätzlich dadurch gestützt, dass die Aberkennung eines ungültigen Ausweises bereits in Anwendung von <ref-law> i.V.m. <ref-law> von Gesetzes wegen zu erfolgen habe. Der österreichische Führerausweis des Beschwerdeführers aus dem Jahr 1999 sei demnach auf unbestimmte Zeit abzuerkennen. Der im Jahr 2003 ausgestellte schweizerische Führerausweis sei ungültig, weil er auf einer ungenügenden materiellen Umtauschgrundlage beruht habe.
Soweit der Beschwerdeführer weiter vorbringt, er habe einen "EU-Führerschein", dessen Gültigkeit von der ausstellenden Behörde laufend bestätigt worden sei, hat die Vorinstanz in ihrem sorgfältig begründeten Entscheid dargelegt, dass es sich auch dabei nicht um eine neue materielle Berechtigungsgrundlage handeln könne. Zwar sei dem Beschwerdeführer zuzustimmen, dass weder dem Auszug aus dem Führerscheinregister des Verkehrsamtes Wien noch der eingereichten Kopie seines österreichischen Führerausweises aus dem Jahr 2006 ein Code 71 ("Duplikat Führerausweis") zu entnehmen sei. Das sei jedoch belanglos, da es sich gemäss den Auskünften der österreichischen Behörden zweifellos um ein Duplikat handle, das gestützt auf den mangels bestehender Fahrerlaubnis in Deutschland zu Unrecht erteilten Duplikat-Ausweis im Jahr 1999 ausgestellt worden sei. Insoweit sei es nicht zutreffend, dass dem Beschwerdeführer in Österreich im Jahr 2006 eine neue Fahrerlaubnis im Sinne einer neuen materiellen Lenkberechtigung erteilt worden sei. Zusammenfassend beruhten alle österreichischen Ausweise und der Schweizer Ausweis auf einer ungültigen Grundlage (d.h. dem entzogenen deutschen Führerausweis). Demzufolge sei der ausländische Führerausweis in der Schweiz abzuerkennen. Gestützt auf den zu Unrecht erstellten schweizerischen Ausweis könne daher auch keine neue schweizerische Fahrberechtigung ausgestellt werden.
4.5. Diese vorinstanzlichen Ausführungen sind nicht zu beanstanden und werden vom Beschwerdeführer, der weitgehend appellatorische Kritik übt und lediglich seine Rechtsauffassungen bekräftigt, ohne weiter aufzuzeigen, inwiefern die Vorinstanz Bundesrecht verletzt haben soll, auch nicht rechtsgenüglich gerügt (<ref-law>). Darauf ist nicht einzutreten.
5.
Bei diesem Ausgang des Verfahrens ist die Beschwerde abzuweisen, soweit darauf einzutreten ist. Da die Bedürftigkeit des Beschwerdeführers nicht belegt ist, kann dem Gesuch um unentgeltliche Rechtspflege nicht entsprochen werden (<ref-law>). Damit trägt der Beschwerdeführer die Kosten (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdeführer auferlegt.
3.
Dieses Urteil wird dem Beschwerdeführer, dem Strassenverkehrsamt des Kantons Luzern, dem Kantonsgericht Luzern, 4. Abteilung, Einzelrichter, und dem Bundesamt für Strassen, Sekretariat Administrativmassnahmen, schriftlich mitgeteilt.
Lausanne, 14. Juni 2017
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Merkli
Der Gerichtsschreiber: Misic