Статский советник (1911). Из шведского рода, один из представителей которого приехал в Россию в XVII в. Внук исследователя Русского Севера Матвея Матвеевича Геденштрома (1781-1845), сын ротмистра Матвея Матвеевича Геденштрома. Родился в Одессе. Окончил юридический факультет Киевского университета в 1882, поступил на службу в Киевскую судебную палату, откуда через год уволился по собственному желанию. Следующие несколько лет провёл в путешествиях по Востоку. В частности, в 1886 был направлен Парижским географическим коммерческим обществом на север острова Суматра для исследования султаната Ачех. Стал первым европейцем, проникшим вглубь Ачеха, где открыл богатое месторождение россыпного золота. В Россию вернулся в 1890 и поступил на службу в МВД. С 1892 чиновник по особым поручениям при Томском губернаторе, затем правитель канцелярии военного губернатора Амурской области.
В марте 1900 обратился к имп. Николаю II с прошением о переводе на службу в МИД и 26.04 прошение было удовлетворено. В апреле 1900 Геденштром назначен вице-консулом в Хакодате, где выполнял секретные задания МИД и Морского министерства, в том числе наблюдал за японскими военными приготовлениями в преддверии русско-японской войны 1904-1905 и японским рыболовством в российских водах. Этнограф В.Л. Серошевский в 1903 писал вице-президенту Императорского Русского географического общества П.П. Семёнову-Тян-Шанскому: «Матвей Матвеевич ... дельный, умный, талантливый человек, знает говорить по-японски и несколько лет уже живет в Хакодате, этом боевом русско-японском пункте. Он правда может рассказать много интересного о складывающихся теперь новых русско-японских отношениях. Он оказал мне и вообще оказывает всяким учёным исследователям большую и сердечную поддержку».
18.01.1902 произведён в надворные советники. В апреле 1903 временно исполнял обязанности русского консула в Сингапуре, а после начала русско-японской войны командирован во Французское Сомали для наблюдения за морскими путями, идущими от Суэцкого канала по Красному морю к проливу Баб-эль-Мандеб, с целью обеспечения безопасности от японской разведки и диверсий при
прохождении российских военных судов. С августа 1906 — российский консул на Мальте. 22.06.1907 подписан приказ о назначении Геденштрома консулом в Мельбурн, куда он прибыл 18.02.1908. С июля 1908 - генеральный консул. Главную задачу на этом посту Геденштром видел в том, чтобы помочь русскому правительству «выяснить какую ценность и величину может представлять Австралия в глазах европейских и некоторых других государств», «какую величину она может представлять из себя… в будущем». За полтора года работы в Австралии консул написал более 2000 листов рукописных донесений, среди них - очерки «О международном положении Австралии» (июль 1908), «Об экономическом и политическом положении Австралии» (декабрь 1908), «О настроении общественного мнения Австралии в виду военно-морских вооружений Германии» (август 1909) и «О движении социализма в Австралии» (сентябрь 1909). В них Геденштром пытается спрогнозировать перспективы внутриполитического развития Австралии, определить ее место в современном мире. Он высоко оценивал степень экономического развития страны и уровень жизни ее белого населения, предсказывал значительную роль, которую Австралия «призвана играть, быть может, не в очень отдаленном будущем». При этом выражал крайнее неприятие социальной политики австралийских лейбористов, резко критиковал чрезмерное, по его мнению, влияние профсоюзов и социалистических элементов в общественной жизни и считал, что цветущее состояние Австралии достигнуто «не благодаря», а, скорее, «несмотря на социалистов». Добился расширения консульской службы в Австралии за счёт учреждения в 1908 нештатных консульств в Брисбене и Аделаиде с их подчинением генконсульству в Мельбурне и назначения в 1909 нештатного вице-консула в Мельбурн.
В октябре 1909 отправился с женой в отпуск на Цейлон, и к месту службы больше не возвращался. 26.07.1910 по собственному прошению освобождён от должности, но остался «состоящим в ведомстве» МИД. После начала первой мировой войны был негласным агентом МИДа в Милане, где установил контакт с Б. Муссолини. В 1915 через Геденштрома Муссолини предложил русскому правительству профинансировать усиление печатной пропаганды и помочь деньгами для организации вооруженной стычки на итало-австрийской границе как возможного повода для вовлечения Италии в войну. Геденштром вернулся в Россию для обсуждения этого предложения в правительственных и военных ведомствах, однако после вступления в конце мая 1915 Италии в войну предложение Муссолини потеряло свою актуальность.
За службу удостоен ордена Св. Станислава 3-й степ. (17.04.1905).
В августе 1917 Геденштром покинул Петроград, в мае 1921 вместе с женой перебрался в Эстонию. Дальнейшая судьба неизвестна.
В документах МИД встречается отзыв о Геденштроме как о человеке «умном, воспитанном <...>, осторожном в деловых отношениях».
Был женат на баронессе Марии Дмитриевне Стюарт, дочери Д.Ф. Стюарта. В Австралии она на общественных началах возглавляла отделение «Альянс Франсез» – общества по распространению французского языка и культуры в штате Виктория.
