Sachverhalt:
A. Bei einer Polizeikontrolle vom 3. September 2007 wurde beim Fahrzeuglenker X._ eine Blutalkoholkonzentration von mindestens 2,54 o/oo festgestellt, worauf ihm der Führerausweis vorsorglich entzogen und er einer verkehrsmedizinischen Untersuchung durch das Institut für Rechtsmedizin der Universität Zürich (IRMZ) zugewiesen wurde. Bereits am 25. September 1999 war X._ der Führerausweis für die Dauer von zwei Monaten entzogen worden, da er mit einer Blutalkoholkonzentration von mindestens 1,08 o/oo ein Fahrzeug gelenkt hatte.
Bei der im Rahmen der verkehrsmedizinischen Begutachtung von X._ am 29. Januar 2008 vorgenommenen chemisch-toxikologischen Haaruntersuchung wurde eine Konzentration von 158 pg Ethylglucuronid (EtG) pro mg Haar nachgewiesen. Im verkehrsmedizinischen Gutachten des IRMZ vom 22. Februar 2008 wurde insbesondere unter Bezugnahme auf dieses Untersuchungsergebnis zusammenfassend festgehalten, bei X._ bestehe eine verkehrsrelevante Alkoholproblematik im Sinne eines regelmässigen Alkoholkonsums und einer Alkoholgewöhnung, weshalb die Fahreignung zum aktuellen Zeitpunkt aus verkehrsmedizinischer Sicht nicht bejaht werden könne. Für eine positive Beurteilung der Fahreignung müsse eine mindestens sechsmonatige Alkoholabstinenz nachgewiesen werden.
Am 18. März 2008 verfügte das Departement des Innern des Kantons Solothurn einen Sicherungsentzug des Führerausweises auf unbestimmte Zeit. Voraussetzung für die Wiedererteilung des Führerausweises sei eine mindestens sechsmonatige, ärztlich nachgewiesene Alkoholabstinenz. Eine dagegen erhobene Beschwerde ans Verwaltungsgericht des Kantons Solothurn zog X._ später wieder zurück.
B. Bei einer erneuten chemisch-toxikologischen Haaruntersuchung auf EtG am 29. Juli 2008 konnte für den untersuchten Zeitraum von Mitte März bis Mitte Juli 2008 kein EtG nachgewiesen werden. In seinem Gutachten vom 14. August 2008 bejahte das IRMZ daher die Fahreignung von X._ unter bestimmten Auflagen.
Am 19. September 2008 verfügte das Departement des Innern die Wiedererteilung des Führerausweises unter Auflagen. Es ordnete an, X._ habe sich nach Ablauf von sechs Monaten einer verkehrsmedizinischen Kontrolluntersuchung inklusive Haarprobe zu unterziehen. Für diese Untersuchung habe er sich im Februar 2009 (nicht vorher und nicht später) anzumelden. Zum Nachweis der Alkoholabstinenz habe er zudem beim Hausarzt im November 2008 die Laborwerte (CDT, Gamma-GT, GOT, GPT und MCV) bestimmen zu lassen. Eine Missachtung der Auflagen habe den sofortigen vorsorglichen Entzug des Führerausweises zur Folge.
C. Am 20. März 2009 teilte das Departement des Innern X._ mit, es sei ein Administrativverfahren gegen ihn eröffnet worden, da er sich keiner erneuten verkehrsmedizinischen Begutachtung inklusive Haaranalyse unterzogen habe. Ihm werde eine Nachfrist bis 8. Mai 2009 gesetzt, um dies nachzuholen.
Mit Schreiben vom 24. April 2009 ans Departement des Innern antwortete X._, er habe die Diagnose "bösartiger Tumor im Halsbereich" erhalten und müsse sich einer mehrwöchigen Strahlen- und Chemotherapie unterziehen. Da er täglich für die Therapie ins Spital fahren müsse, sei es für ihn wichtig, dass er den Führerausweis behalten könne. Er beantrage deshalb die Einstellung des Administrativverfahrens. Das Departement des Innern erklärte sich mit Schreiben vom 28. April 2009 bereit, die Frist zur Vornahme der Kontrolluntersuchung bis Ende November 2009 aufzuschieben.
Gemäss Aktennotiz vom 14. Januar 2010 teilte X._ telefonisch mit, er werde versuchen, die Untersuchung bis Ende März 2010 durchzuführen.
Mit Schreiben vom 29. Oktober 2010 erkundigte sich das Departement des Innern bei X._ nach dessen Gesundheitszustand. Nachdem X._ sich nicht gemeldet hatte, wurde ihm am 23. Dezember 2010 der Sicherungsentzug des Führerausweises auf unbestimmte Zeit angedroht, da er der Aufforderung zur Durchführung einer verkehrsmedizinischen Kontrolluntersuchung nicht nachgekommen sei und der Verdacht auf mangelnde Fahreignung bestehe.
Am 7. Januar 2011 teilte X._ mit, nach der Krebsdiagnose im März 2009 habe er im Juli 2009 auch noch einen Hirnschlag erlitten. Jetzt gehe es aber langsam wieder aufwärts. Da der Vorfall vom 3. September 2007 nun mehr als drei Jahre zurückliege und er seither keine Vergehen im Strassenverkehr mehr begangen habe, hoffe er, den Führerausweis ohne weitere Massnahmen behalten zu dürfen.
Am 4. Februar 2011 gewährte das Departement des Innern X._ eine weitere Frist bis zum 31. März 2011, um sich der Kontrolluntersuchung inklusive Haaranalyse zu unterziehen. Bei unbenutzt verstrichener Frist werde ein Sicherungsentzug des Führerausweises auf unbestimmte Zeit verfügt, wozu X._ das rechtliche Gehör erteilt wurde. Die Frist zur Stellungnahme und zur Kontrolluntersuchung wurde in der Folge auf Gesuch von X._ hin bis zum 30. April 2011 verlängert. Mit Stellungnahme vom 25. April 2011 beantragte dieser, von der Kontrolluntersuchung mit Haarprobe sei abzusehen, und ihm sei der Führerausweis ohne Auflagen zu belassen.
D. Mit Verfügung des Departements des Innern vom 10. Mai 2011 wurde X._ der Führerausweis auf unbestimmte Zeit entzogen. Das Departement erwog, die rechtskräftig angeordnete Auflage sei nicht erfüllt und der Nachweis der Alkoholabstinenz nicht erbracht worden.
Die von X._ gegen diesen Entscheid geführte Beschwerde wies das Verwaltungsgericht mit Urteil vom 14. Oktober 2011 ab.
E. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten ans Bundesgericht vom 16. November 2011 beantragt X._, das Urteil des Verwaltungsgerichts vom 14. Oktober 2011 und die Verfügung des Departements des Innern vom 10. Mai 2011 seien aufzuheben, und ihm sei der Führerausweis umgehend und per sofort wieder zu erteilen.
Das Verwaltungsgericht beantragt in seiner Vernehmlassung vom 12. Dezember 2011, die Beschwerde sei abzuweisen, soweit darauf eingetreten werden könne. Mit Stellungnahme vom 14. Dezember 2011 stellt das Departement des Innern Antrag auf Beschwerdeabweisung. Den gleichen Antrag stellt das Bundesamt für Strassen ASTRA in seiner Eingabe vom 24. Januar 2012. Diese Stellungnahmen wurden dem Beschwerdeführer zur Kenntnisnahme zugestellt.
Mit Präsidialverfügung vom 17. Januar 2012 wurde das von X._ gestellte Gesuch, der Beschwerde die aufschiebende Wirkung zuzuerkennen, gutgeheissen.

Erwägungen:
1. Mit dem angefochtenen Entscheid bestätigte die Vorinstanz den vom Departement des Innern am 10. Mai 2011 verfügten Entzug des Führerausweises des Beschwerdeführers. Angefochten ist somit ein letztinstanzlicher kantonaler Entscheid in einer öffentlich-rechtlichen Angelegenheit (vgl. Art. 82 lit. a und Art. 86 Abs. 1 lit. d und Abs. 2 BGG). Der Beschwerdeführer ist nach Art. 89 Abs. 1 BGG zur Beschwerde legitimiert. Da auch die übrigen Sachurteilsvoraussetzungen erfüllt sind, ist auf die Beschwerde grundsätzlich einzutreten. Soweit der Beschwerdeführer jedoch zugleich die Aufhebung der Verfügung des Departements des Innern vom 10. Mai 2011 beantragt, kann auf die Beschwerde nicht eingetreten werden. Diese Verfügung ist durch den Entscheid der Vorinstanz ersetzt worden (Devolutiveffekt) und gilt als inhaltlich mit angefochten (vgl. <ref-ruling> E. 1.4 S. 144 mit Hinweis).
2. 2.1 Der Beschwerdeführer macht geltend, mit Verfügung vom 19. September 2008 sei er nicht verpflichtet worden, bis heute alkoholabstinent zu sein. Eine rund vierjährige totale Alkoholabstinenz zu verlangen, wie dies faktisch gemacht werde, sei völlig unverhältnismässig und missachte das Rechtsgleichheitsgebot (Art. 8 Abs. 1 BV), das Nichtdiskriminierungsverbot (Art. 8 Abs. 2 BV) und das Willkürverbot (Art. 9 BV). Dass die Haarprobenanalyse im Februar 2009 nicht habe vorgenommen werden können und das Verfahren nunmehr so lange gedauert habe, sei nicht durch ihn verschuldet, sondern auf die gesundheitlichen Schicksalsschläge zurückzuführen. Ihm sei der Führerausweis bereits im August 2008 wieder erteilt worden, und er habe seither unfallfrei und ohne jegliche Verzeigung am Strassenverkehr teilgenommen. Damit sei seine Fahreignung hinlänglich nachgewiesen, sodass kein Anlass mehr für weitere Kontrollen bestehe. Das Festhalten an einer Kontrolluntersuchung sei im Ergebnis rechtsmissbräuchlich, unverhältnismässig und wider das Legalitätsprinzip.
2.2 Die Vorinstanz hat zusammenfassend erwogen, eine Kontrolluntersuchung mittels Haarprobenanalyse sei dringend notwendig, um überprüfen zu können, ob der Beschwerdeführer sein Alkoholproblem wirklich überwunden habe und keine Gefahr für die Verkehrssicherheit darstelle. Da der Beschwerdeführer die rechtskräftig verfügte Auflage der Kontrolluntersuchung nicht erfüllt habe, sei ihm der Führerausweis zu Recht erneut entzogen worden.
2.3 Führerausweise sind zu entziehen, wenn festgestellt wird, dass die gesetzlichen Voraussetzungen zur Erteilung nicht oder nicht mehr bestehen (Art. 16 Abs. 1 SVG). Ein Sicherungsentzug auf unbestimmte Zeit erfolgt insbesondere, wenn der Lenker an einer Sucht leidet, welche seine Fahreignung ausschliesst (Art. 16d Abs. 1 lit. b SVG). Der gestützt auf eine Fahreignungsabklärung im Sinne von Art. 16d SVG auf unbestimmte Zeit entzogene Führerausweis kann bedingt und unter Auflagen wiedererteilt werden, wenn eine allfällige gesetzliche oder verfügte Sperrfrist abgelaufen ist und die betroffene Person die Behebung des Mangels nachweist, der die Fahreignung ausgeschlossen hat (Art. 17 Abs. 3 SVG). Missachtet die betroffene Person die Auflagen oder missbraucht sie in anderer Weise das in sie gesetzte Vertrauen, so ist der Ausweis wieder zu entziehen (Art. 17 Abs. 5 SVG).
Staatliche Eingriffe in die persönliche Freiheit müssen auf einer gesetzlichen Grundlage beruhen, im öffentlichen Interesse liegen und verhältnismässig sein (Art. 10 Abs. 2 i.V.m. Art. 36 BV). Nach der Praxis des Bundesgerichts kann die Wiedererteilung des Führerausweises im Sinne von Art. 17 Abs. 3 SVG (nach einem Sicherungsentzug wegen Alkohol- oder Drogensucht bzw. einer entsprechenden Fahreignungsabklärung) insbesondere an die Auflage einer befristeten und ärztlich kontrollierten Suchtabstinenzkontrolle geknüpft werden. In der Regel hat die medizinische Nachkontrolle (nach Ablauf einer Sperrfrist bzw. Probezeit) mindestens ein Jahr zu dauern. Die Auflage, während der betreffenden Zeit abstinent zu leben und dies ärztlich kontrollieren zu lassen, steht in diesen Fällen in unmittelbarem Zusammenhang mit der Überwindung einer Suchtkrankheit, welche die Fahreignung des Betroffenen beeinträchtigt. Der damit verbundene Eingriff in die Persönlichkeitsrechte erscheint im Interesse der Verkehrssicherheit gerechtfertigt (<ref-ruling> E. 3.2 S. 28 f.; <ref-ruling> E. 2.2 S. 84). Vermag die betroffene Person in einem solchen Fall die mit der Wiedererteilung des Führerausweises auferlegte, befristete und ärztlich kontrollierte Abstinenz nicht einzuhalten, ist ihr der Ausweis in Anwendung von Art. 16 Abs. 1 Satz 2 sowie Art. 17 Abs. 5 SVG wieder zu entziehen. Während beim Sicherungsentzug nach Art. 16d Abs. 1 lit. b SVG sorgfältigen verkehrsmedizinischen Abklärungen grosse Bedeutung zukommt (vgl. BGE <ref-ruling> E. 6.2.2 S. 91; Urteil 1C_150/2010 vom 25. November 2010 E. 5), rechtfertigt die Nichteinhaltung einer mit der Wiedererteilung des Führerausweises verknüpften Bedingung den erneuten Entzug des Ausweises, ohne dass zuvor noch einmal verkehrsmedizinische Abklärungen hinsichtlich der Fahreignung notwendig wären (Urteil 1C_26/2011 vom 25. Juli 2011 E. 4.1).
Da der Beschwerdeführer im März 2009 an einem bösartigen Tumor erkrankte und im Juni 2009 einen Hirnschlag erlitt, wurde die Kontrolluntersuchung auf sein Ersuchen hin mehrmals aufgeschoben. Das Departement des Innern hat dabei jedoch immer an der rechtskräftig verfügten Auflage festgehalten.
2.4 Auszugehen ist von folgendem, von der Vorinstanz willkürfrei festgestellten Sachverhalt: Bei der im Rahmen der verkehrsmedizinischen Begutachtung des Beschwerdeführers vorgenommenen chemisch-toxikologischen Haaruntersuchung vom 29. Januar 2008 wurde eine sehr hohe Konzentration von 158 pg EtG pro mg Haar nachgewiesen (gemäss der Publikation "Bestimmung von Ethylglucuronid [EtG] in Haarproben" der Schweizerischen Gesellschaft für Rechtsmedizin [SGRM], Arbeitsgruppe Haaranalytik, Version 12/2009 [zur Publikation freigegeben am 27. Januar 2010], werden EtG-Analyseergebnisse von bis zu 30 pg pro mg Haar als moderater Alkoholkonsum ["Social-Drinking / Low-Risk-Drinking"], solche von über 30 pg pro mg Haar als risikoreicher Alkoholkonsum ["High-Risk-Drinking" bzw. "starker bis chronisch-exzessiver Alkohol-Konsum"] bezeichnet; vgl. hierzu auch Urteil 1C_243/2010 vom 10. Dezember 2010 E. 2.7). Im Gutachten des IRMZ vom 22. Februar 2008 wurde deshalb gefolgert, der Beschwerdeführer leide an einer die Fahreignung ausschliessenden Alkoholsucht. Nach dem Nachweis einer sechsmonatigen Alkoholabstinenz wurde dem Beschwerdeführer der Führerausweis mit Verfügung vom 19. September 2008 insbesondere unter der Auflage wieder erteilt, sich nach Ablauf von sechs Monaten erneut einer verkehrsmedizinischen Kontrolluntersuchung inklusive Haarprobe zu unterziehen, wobei eine Missachtung der Auflage den sofortigen vorsorglichen Entzug des Führerausweises zur Folge habe. Diese Verfügung vom 19. September 2008 erwuchs unangefochten in Rechtskraft.
2.5 Der Beschwerdeführer hat die in der Verfügung vom 19. September 2008 mit der Wiedererteilung des Führerausweises verknüpfte Auflage der verkehrsmedizinischen Kontrolluntersuchung inklusive Haaranalyse nicht erfüllt. Ihm ist daher der Führerausweis in Anwendung von Art. 16 Abs. 1 Satz 2 sowie Art. 17 Abs. 5 SVG zu Recht wieder entzogen worden, und zwar ohne dass zuvor erneut verkehrsmedizinische Abklärungen hinsichtlich seiner Fahreignung hätten vorgenommen werden müssen.
Die vom Beschwerdeführer dagegen erhobenen Einwände sind nicht stichhaltig. Insbesondere kann nicht gesagt werden, der Führerausweisentzug erweise sich nicht mehr als erforderlich, denn mangels verkehrsmedizinischer Kontrolluntersuchung ist ungeklärt, ob der Beschwerdeführer seine Alkoholsucht tatsächlich überwunden hat. Eine solche Untersuchung stellt ein geeignetes, notwendiges und verhältnismässiges Mittel zur Gewährleistung der Verkehrssicherheit dar, d.h. die Auflage ist trotz des damit verbundenen Eingriffs in den Persönlichkeitsbereich des Beschwerdeführers gerechtfertigt. Entgegen dem Vorbringen des Beschwerdeführers wird von ihm insoweit nicht eine vierjährige Alkoholabstinenz, sondern eine solche von sechs Monaten verlangt, welche mittels Haarprobenanalyse nachzuweisen ist. Im Übrigen ist die relativ lange Verfahrensdauer - der Beschwerdeführer hätte sich bereits im Februar 2009 der Untersuchung unterziehen müssen, der Führerausweis wurde jedoch erst mit Verfügung vom 11. Mai 2011 erneut entzogen - nicht dem Departement des Innern anzulasten. Vielmehr hat dieses mit diversen Fristerstreckungen den Anträgen des Beschwerdeführers entsprochen und seiner schwierigen gesundheitlichen Situation Rechnung getragen.
Soweit der Beschwerdeführer schliesslich Verstösse gegen das Rechtsgleichheitsgebot (Art. 8 Abs. 1 BV), das Nichtdiskriminierungsverbot (Art. 8 Abs. 2 BV) und das Willkürverbot (Art. 9 BV) behauptet (vgl. E. 2.1 hiervor), sind die Rügen nicht hinreichend begründet, weshalb darauf nicht einzutreten ist (Art. 42 Abs. 2 BGG).
Zusammenfassend ist festzuhalten, dass der Beschwerdeführer den Beleg einer sechsmonatigen Alkoholabstinenz mittels Haarprobenanalyse nicht erbracht hat, und dass sich das Festhalten an dieser rechtskräftig verfügten Auflage der Kontrolluntersuchung weder als rechtsmissbräuchlich noch als unverhältnismässig erweist. Der Führerausweisentzug verletzt damit kein Bundesrecht.
3. Die Beschwerde ist abzuweisen, soweit darauf einzutreten ist. Bei diesem Ausgang des Verfahrens trägt der Beschwerdeführer die Gerichtskosten (Art. 66 Abs. 1 BGG).

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 Departement des Innern und dem Verwaltungsgericht des Kantons Solothurn sowie dem Bundesamt für Strassen, Sekretariat Administrativmassnahmen, schriftlich mitgeteilt.
Lausanne, 5. März 2012
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Fonjallaz
Der Gerichtsschreiber: Stohner