Родился 15.12.1918 г. в с. Жихово (ныне Середино, Будского района Сумской области Украины) в семье крестьянина. Русский. Член КПСС с 1953 г. Окончив 7 классов, работал трактористом. В Красной Армии с 1941 г. Участник Великой Отечественной войны с июня 1941 г. Призван Семикаракорским РВК Ростовской области.
Командир орудия 6-го гвардейского стрелкового полка (2-я гвардейская стрелковая дивизия, 2-я гвардейская армия, 3-й Белорусский фронт) гвардии сержант Титенко отличился 18.03.1945 г. в бою за укреплённый пункт врага Прейсиш-Тирау. Ворвавшись туда, расчёт оказался отрезанным от стрелковых подразделений. Организовав круговую оборону, 4 часа отбивал контратаки противника.
Из наградного листа:
«18 марта 1945 г. полк вышел на подступы к опорному пункту – селению Прейсиш-Тирау (Восточная Пруссия). Бои на этом участке принимали все более ожесточенный характер, по мере того как кольцо окружения Восточно-Прусской группировки немцев, образованное войсками Красной Армии, сжималось все теснее. По направлению движения полка противник отчаянно сопротивлялся, цепляясь не только за населенные пункты и отдельно стоящие дворы, но и за складки местности, перелески, водные рубежи. Непрерывно контратакуя наши наступающие подразделения, противник поддерживал свои контратаки сильным пулеметным и минометным огнем, а также огнем самоходной артиллерии, которую он использовал в большинстве случаев, не считаясь с потерями, – на прямой наводке. Противник создавал сильный заградительный огонь при продвижении наших частей. В этих условиях 18 марта полк приступил к выполнению задачи по овладению населенным пунктом Прейсиш-Тирау, который особо ожесточенно оборонялся немцами. Действуя исключительно смело и решительно, тов. Титенко со своим расчетом значительно опередил боевые порядки пехоты и, несмотря на сильный заградительный огонь противника, стремительно ворвался на окраину населенного пункта. Немцы встретили сильным пулеметным и минометным огнем смелый расчет советских артиллеристов. Орудие Титенко оказалось отрезанным от боевых порядков пехоты сильным огневым валом, который образовал противник. Сразу же были убиты 2 лошади орудийного расчета. Немецкая пехота начала обходить расчет с флангов, видимо, с целью захвата его в плен. Тов. Титенко приказал расчету занять круговую оборону и открыть огонь по врагу. Немцы открыли пулеметный огонь по расчету из окна дома. Тов. Титенко встал за орудие и прямой наводкой уничтожил пулемет вместе с его прислугой. Тогда немцы открыли по нему огонь из другого пулемета с противоположной стороны. Тов. Титенко уничтожил и второй пулемет противника. Немцы открыли по гвардейцам шквальный огонь и предприняли атаку. Тов. Титенко открыл беглый огонь по пехоте противника и заставил ее отойти. Осколком вражеской мины тов. Титенко был ранен. Превозмогая боль, он продолжал бить наседавшего врага, огонь вел точный, экономя боеприпасы. Около четырех часов тов. Титенко со своим расчетом отбивался от врага и, как потом выяснилось, уничтожил свыше 30 немцев, разбил 4 станковых пулемета противника. Когда подошла наша пехота и потеснила противника, тов. Титенко, разгоряченный боем, продолжал еще сражаться и в это время был ранен вторично. В тяжелом бессознательном состоянии он был эвакуирован с поля боя. Только за период боев на территории Восточной Пруссии тов. Титенко огнем своего орудия уничтожил 10 станковых и 7 ручных пулеметов противника, истребив большую часть их прислуги, подавил огонь противотанкового орудия, разбил 4 автомашины с военными грузами немцев, вывел из строя убитыми и ранеными до 150 немецких солдат и офицеров.
За выдающееся мужество и героизм, проявленные в боях с врагом, высокое боевое мастерство и волю к победе, за нанесение врагу большого урона в живой силе и вооружении, в результате чего для наступающей пехоты были обеспечены благоприятные условия ведения наступательного боя и овладения населенным пунктом, тов. Титенко достоин присвоения высокого звания – «Герой Советского Союза».
За этот подвиг 19 апреля 1945 г. Андрею Лаврентьевичу Титенко было присвоено звание Героя Советского Союза с вручением ордена Ленина и медали «Золотая Звезда» (№7801).
В 1945 г. демобилизовался. Трудился на мельницах в Калмыкии, в станицах Григорополисская и Новотроицкая Ставропольского края.
С 1954 г. живёт в г. Изобильный Ставропольского края. Заведовал мельницей, долгое время работал директором пищекомбината, 27 лет возглавлял пожарную команду на Изобильненском элеваторе.
Награждён орденами Ленина, Отечественной войны I ст., Славы III ст., медалями.
Почётный гражданин Изобильненского района. Имя Героя носит переулок в г. Изобильный Ставропольского края.