Корабельный мастер, родился в 1773 году в дворянской семье. Построил более 40 судов различного ранга и класса для Российского императорского флота, в том числе первый колёсный пароход Черноморского флота.
В 1785 году Андрей Мелихов был принят на службу корабельным учеником 2-го класса в чертёжную мастерскую Санкт-Петербургского адмиралтейства. В 1789 году был произведён в корабельные ученики 1-го класса. В 1789—1790 годах на верфях в Санкт-Петербурге и Кронштадте участвовал в строительстве фрегатов, палубных батарей, канонерских лодок, полупрамов, шебек и других судов под руководством корабельного мастера Даниила Масальского.
Самостоятельную кораблестроительную деятельность Мелихов начал на Охтенской верфи Санкт-Петербурга, где в 1790 году построил два небольших судна — галета (легкие двухмачтовые парусники), участвовал в строительстве канонерских лодок и четырех плавучих батарей. За проявленное усердие в период строительства был награждён годовым жалованьем. В 1791 году он участвовал в постройке двух полупрамов. В 1792 году Мелихов участвовал в постройке 74-пушечного корабля «Святая Елисавета», который строили корабельные мастера Кольман и В. Сарычев. В этом же году Мелихов был произведён в тиммерманы. В 1793—1794 годах под руководством корабельного мастера Масальского принимал участие в постройке 38-пушечного фрегата «Елизавета» и одного брига.
В 1794—1800 годах Мелихов неоднократно выезжал в Англию для обучения кораблестроению. За предоставление всевозможных чертежей, отчётов и записок о командировке поощрялся денежными премиями: в 1796 году ему было объявлено «благоволение» от Государственной коллегии Адмиралтейства, в 1798 году — за присылку из Англии моделей, планов и заметок, касающихся кораблестроения, получил в награду 50 фунтов стерлингов, в 1800 году — за присылку из Англии чертежей и записок на заготовку леса вновь получил в награду 50 фунтов стерлингов. С 1795 по 1798 годы в Санкт-Петербургском адмиралтействе Мелихов совместно с корабельным мастером В. Сарычевым строил 38-пушечный фрегат «Богоявление Господне» (заложен 7 марта 1795 года, спущен на воду 24 сентября 1798 года), а с 1796 по 1800 годы совместно с мастером П. Васильевым строил фрегат «Эммануил».
В 1799 году Мелихов переведён в корабельные подмастерья 12 класса Табеля о рангах. В 1800—1805 годах продолжал работать в Санкт-Петербургском адмиралтействе под руководством корабельного мастера В. Сарычева, совместно с которым заложил в августе 1802 года 74-пушечные линейные корабли «Твёрдый» и «Скорый». В том же году был командирован в Новгородскую губернию для осмотра передаваемой в казну дачи, вернувшись в Санкт-Петербург продолжал постройку «Твёрдого», параллельно в 1803 году в Главном гребном порту построил десять канонерских лодок, тридцать иолов, восемь плавучих батарей и пакетботов. В 1804 году за строительство корабля «Твердый» получил в награду 300 руб. В 1803—1804 годах находился под начальством интендантской экспедиции, с 1804 служил под руководством директора кораблестроения Брюн де Сен-Катерина и произведён в 11 класс Табеля о рангах. В 1805 году достраивал и 18 июля спустил на воду линейный корабль «Твёрдый», осуществил проводку его на камелях до Кронштадта, за что ему от Государственной коллегии Адмиралтейства была объявлена благодарность.
В 1806 году Мелихов построил и спустил на воду два 14-пушечных катера и два пакетбота, исправил и достроил шлюп «Диана», за что получил благодарность от Государственной коллегии Адмиралтейства. 14 марта 1801 года Мелихов был произведён в корабельные мастера 6 класса Табеля о рангах. В 1807—1808 годах строил два бомбардирских судна, заложил и совместно с Брюн де Сен-Катерином и И. В. Курепановым строил 88-пушечный корабль «Смелый», а также 48-пушечный фрегат. В 1808 году построил и спустил на воду два бомбардирских судна. В это же время осуществлял ремонт кораблей гребного флота, построил два люгера, двадцать пять ластовых судов, два брига, и спустил их на воду. Находился при проводке на камелях корабля «Смелый», фрегата «Валера». За постройку и спуск вышеуказанных кораблей ему было объявлено «благоволение» от Государственной коллегии Адмиралтейства, а также дано право на объявление такого же «благоволения» его подчинённым, находившимся при строительстве. От исполнительной экспедиции Мелихов был представлен к награждению орденом Святого Владимира четвёртой степени, и за особое усердие в работе награждён премией в 500 рублей на путевые издержки.
17 февраля 1809 года Мелихов был командирован на Черноморский флот, сначала в город Николаев, а 6 июня в Севастополь. По поручению Черноморской исполнительной экспедиции в Феодосии осматривал брандвахты. 29 августа 1809 года был направлен в Керченский порт для осмотра канонерских лодок. В 1809—1816 годах находился в распоряжении Севастопольской конторы. В 1809 году в Севастопольском порту осуществлял ремонт судов, в том числе 11-пушечных кораблей «Ягудиил» и «Победа», которые ранее были признаны негодными к плаванию. За восстановление этих кораблей получил «благоволение» от Главного Черноморского департамента и «письменную признательность» от начальника Севастопольской конторы адмирала Сарычева и контр-адмирала Галла. В 1810 году достроил и спустил 18-пушечный корвет «Крым». В 1812—1813 годах продолжал руководить ремонтом кораблей флота, построил и спустил на воду 16-пушечный бриг «Мингрелия». В 1815 году руководил строительством второго стапеля на севастопольской верфи, в том же году построил и спустил на воду 24-пушечный корвет «Язон» и заложил 14-пушечную шхуну «Севастополь», которую спустил на воду 16 мая 1818 года.
В 1816 году руководил ремонтом кораблей Черноморской эскадры, направляемой в поход, а затем был переведён в Николаевский порт, где 21 мая 1817 года приступил к постройке 74-пушечного линейного корабля «Норд-Адлер», который достроил и спустил на воду 24 мая 1820 года. В этом же году был награждён орденом Святого Владимира четвёртой степени. 27 апреля 1817 года А. И. Мелихов заложил в Николаевском адмиралтействе 8-пушечный тендер «Андрей», который спустил на воду 9 октября 1817 года. В 1817-1818 годах Мелихов руководил капитальным ремонтом эллинга адмиралтейства с заменой большей части деревянных свай. В 1818 году за постройку и спуск в Николаевском порту 44-пушечного фрегата «Флора» Мелихов получил от Его Императорского величества бриллиантовый перстень. Впервые в отечественном кораблестроении при строительстве фрегата «Флора» Мелихов применил систему набора корпуса по методу Сепингса — с диагональными сваями-ридерсами. В 1819 году Мелихов построил и спустил на воду военный транспорт «Мария» и канонерскую образцовую лодку «Дерзкая».
В 1820 году провёл через мелководную реку Буг построенный 74-пушечный корабль «Норд-Адлер», построил и спустил на воду бриг, пароходное судно, военный транспорт большого размера, которые также провёл через мелководье Буга. 24 мая 1820 года в Николаеве Мелихов спустил на воду построенный им первый колёсный пароход «Везувий» из дубового и частично соснового леса с двумя паровыми машинами по 16 л.с., который строился по указанию командующего Черноморским флотом вице-адмирала Грейга для доставки корабельного леса из Херсона в Николаев.
В 1820—1821 годах построил 44-пушечный фрегат «Поспешный» (спущен на воду 2 ноября 1821 года), 22-пушечные бриги «Ганимед» (1820) и «Орфей» (1821), яхту «Утеха» и транспорт «Ингул». Для морского училища спустил на воду корвет. В 1821 году в Херсонском Адмиралтействе построил 110-пушечный корабль «Император Франц». Все суда, построенные Мелиховым на верфях Черноморского флота, участвовали в боевых действиях в русско-турецкую войну 1828—1829 годов.
Умер Андрей Иванович Мелихов в октябре 1821 года в городе Николаеве.
