Geboren am 15. Dezember 1807 in Dahme (Provinz Brandenburg, Königreich Sachsen) als eines von acht Kindern, erlernte Christian Gottlob Teichelmann zunächst den Beruf Zimmermann. 1829 reiste er nach Berlin und nahm Privatunterricht in Algebra, Arithmetik und Geometrie, um sich für seine Aufnahme bei der Königlichen Baugewerbeschule vorzubereiten. Während seiner Zeit an der Baugewerbeschule lernte Teichelmann Schüler des Missionsinstituts von Johannes Jänicke kennen. 1831 verließ Teichelmann daraufhin die Königliche Baugewerbesschule und begann seine theologische Ausbildung.

Am 13. September 1836 wurde er in das neu gegründete Dresdner Missionsseminar aufgenommen. Am 4. Februar 1838 wurde er gemeinsam mit Clamor Wilhelm Schürmann in der Kirche St. Bartholomäi in Altenburg ordiniert und vier Tage später in Dresden nach Australien abgeordnet.
Die beiden Missionare landeten am 14. Oktober 1838 in Adelaide. Teichelmann baute mit geringer finanzieller Unterstützung gemeinsam mit Schürmann die erste Schule für Aborigines in Piltawodli in der Nähe von Adelaide auf. Am 25. Dezember 1843 heiratete er die 21-jährige Engländerin Margarethe Nicholson. Das Ehepaar Teichelmann bekam 14 Kinder.

Er starb am 31. Mai 1888 auf seiner Farm in Haywood Park, Stansbury.