Kuhnlein wuchs auf einem Bauernhof in seinem Geburtsort Unterwössen auf. Er absolvierte eine Schreinerlehre und ging nach seinen Gesellenjahren zum Bundesgrenzschutz. Der Bundesgrenzschutz wurde in den 1970er-Jahren in der Terrorbekämpfung eingesetzt und war mit der RAF, Schleyer-Entführung und Anti-Atomkraft-Demonstrationen konfrontiert. Auch an der Grenze zur DDR war Kuhnlein auf Streife unterwegs. 1981 schied er aus dem Polizeidienst aus, übernahm die Landwirtschaft seiner Tante und arbeitete im Nebenerwerb in einem Schreinerbetrieb. In diesem Lebensabschnitt erkannte er die Kunst für sich. Seit 1983 ist er als freischaffender Bildhauer tätig. Bis heute hatte er weit über hundert Einzelausstellungen und mehr als hundert Ausstellungsbeteiligungen in 15 Ländern.

Kuhnleins Arbeiten entstehen mithilfe von Werkzeugen wie Motorsäge, Flammenwerfer oder Schweißgerät. Kuhnleins Skulpturen zeichnen sich im Besonderen durch ihre zerklüfteten Oberflächen aus.

2001 übernahm Kuhnlein die künstlerische Gestaltung der Ausstellung Otto der Große, Bayern und Europa, die Begleitausstellung zur Europaratausstellung Otto der Große in Magdeburg. Insgesamt fertigte er dafür 30 Skulpturen. Im Rahmenprogramm der 29. Ausstellung des Europarates und Landesausstellung Sachsen-Anhalt 2006 Heiliges Römisches Reich Deutscher Nation errichtete Kuhnlein an zehn Erinnerungsorten Skulpturen, mit denen er historische Persönlichkeiten porträtierte, die einerseits als Identifikationen des heutigen Sachsen-Anhalts gelten und die andererseits mit der Geschichte des Heiligen Römischen Reiches verbunden sind. Den Mittelpunkt dieser Kunstaktion bildete das Kulturhistorische Museum Magdeburg, in dem seit 2003 Kuhnleins Version des Magdeburger Reiters steht. Ebenso fertigte er 2003 die Skulpturengruppe Befreiung für den Märtyreraltar in der Dresdner Kathedrale (Hofkirche). Außerdem wurde ihm die künstlerische Begleitung für die Landesausstellungen 200 Jahre Franken in Bayern 2006 in Nürnberg und Aufbruch in die Gotik 2009 in Magdeburg übertragen. 2007 gestaltete Andreas Kuhnlein den Andachtsraum im Bendlerblock des Bundesverteidigungsministeriums in Berlin.

Unter dem Titel Zerklüftete Antike präsentierte Kuhnlein 2016 seine Werke in der Münchner Glyptothek. 16 extra dafür geschaffene, zerklüftete Holzskulpturen wurden den antiken Meisterwerken gegenübergestellt.

MenschSein war der Titel einer umfangreichen Kuhnlein-Schau, die 2017 von der Städtischen Galerie Rosenheim organisiert wurde.