Als Sohn eines Landwirts wurde Gustav Leuthäußer 1853 in der Domäne Oeslau im heutigen Rödental geboren. Nach dem Besuch der Bürgerschule führte ihn sein Bildungsweg über die Realschule zum Ernst-Albert-Lehrerseminar. 1873 trat er in den städtischen Schuldienst ein.
Seine enge Verbindung zum Turnwesen entwickelte sich in dieser Zeit. 1874 trat er in die Coburger Turngenossenschaft ein und stieg rasch in die Vorstandschaft auf. Im Jahr 1878 wählten ihn die Mitglieder zum ersten Vorsitzenden des Vereins. Dieses Amt sollte er bis zu seinem Tod mit großem Engagement ausüben. Unter seiner Leitung blühte die Turnbewegung in Coburg auf.
Diese Zeit fiel in eine Epoche, in der die deutsche Turnbewegung auch nationalpolitische Bedeutung hatte. Nach der Reichsgründung 1871 wurde Turnen als Instrument der körperlichen Erziehung und staatsbürgerlichen Ertüchtigung verstanden. Überregionale Zusammenschlüsse wie die Turn- und Sportverbände in Thüringen und Franken stärkten den Austausch und das Gemeinschaftsgefühl. Leuthäußer vertrat die Coburger Turnerschaft weit über die Stadtgrenzen hinaus und prägte so die regionale Umsetzung der wachsenden Turnkultur in Deutschland.
Sein Wirken beschränkte sich jedoch nicht allein auf den Sport. 1888 berief ihn das herzogliche Staatsministerium als Turnlehrer in den Staatsdienst. Dort unterrichtete er am Gymnasium, an der Realschule sowie am Lehreseminar und beaufsichtigte zusätzlich den gesamten Volksschul-Turnunterricht des Herzogtums. Damit trug er entscheidend zur Professionalisierung und Institutionalisierung des Turnunterrichts bei. Dieser Prozess vollzog sich im ganzen Reich und war eng mit der zunehmenden Verankerung von Sport in den Lehrplänen verknüpft.
Ein weiteres Feld seiner Tätigkeit war das Feuerlöschwesen. Nach einer praktischen Ausbildung bei der Berliner Feuerwehr erhielt er 1896 die Aufsicht über das Brandschutzwesen im Herzogtum Coburg, das er umsichtig reformierte. Neben seinen organisatorischen Leistungen trat Leuthäußer auch als Mundartdichter hervor. Über 100 Gedichte mit lokalpatriotischem Inhalt zeichnen ein lebendiges Bild Coburgs um die Jahrhundertwende. Seine Werke verbinden Heimatliebe mit humorvoller Beobachtungsgabe. Sein gesellschaftliches Ansehen spiegelte sich auch in seiner Wahl in das Coburger Stadtparlament wider. Als Oberturnlehrer, Landesbrandmeister, Vereinsvorsitzender und Volksdichter war er eine herausragende Persönlichkeit seiner Zeit.
1909 starb Gustav Leuthäußer im Alter von nur 55 Jahren an einer schweren Krankheit. Die Turngenossenschaft ehrte ihn 1910 mit einem Ehrenstein auf dem Coburger Friedhof, der sein Andenken bis heute bewahrt.
Leuthäußer verkörperte eine Generation, die Sport, Bildung und Bürgersinn als Einheit verstand. Sein Wirken steht beispielhaft für die Verankerung des Turnens in der Gesellschaft des Kaiserreichs und für die Verbindung von regionalem Engagement mit überregionalen Entwicklungen im deutschen Sportwesen.