Родился 1 (по новому стилю — 14) сентября 1906 г. в селе Калюжино (ныне — Кегичевский район Харьковской области Украины) в крестьянской семье. Окончил неполную среднюю школу.

В 1927 г. Волошин вступил в ВКП (б). В 1928-1931 гг. он проходил срочную службу в 45-м отдельном Теркском кавалерийском дивизионе войск ОГПУ, принимал участие в боях с бандформированиями на Кавказе. В 1933 г. окончил Курсы командирской переподготовки. После демобилизации он был комсоргом, политруком Зеньковской машинно-тракторной станции Полтавской области Украинской ССР, являлся председателем Зеньковского городского совета депутатов. В 1941 г. Волошин окончил третий курс Харьковского инженерно-экономического института.

В начале Великой Отечественной войны Волошин был повторно призван в армию. С июля 1941 г. — на фронте, первоначально был комиссаром стрелкового батальона на Юго-Западном фронте, был ранен. После излечения политрук Андрей Волошин стал военным комиссаром 3-го отдельного стрелкового батальона 43-й отдельной стрелковой бригады.

Принимал участие в битве за Москву, два раза в ходе нее был ранен. В дальнейшем участвовал в Сталинградской битве, с октября 1942 г. в звании майора командовал 999-м стрелковым полком. На этой должности участвовал в Ростовской наступательной операции и выходе к реке Миус в мае 1943 г. За боевые заслуги полк Волошина, как и вся дивизия, был преобразован в гвардейский, став 295-м гвардейским стрелковым полком.

Участвовал в прорыве немецкой обороны на Миусе в июле 1943 г., Донбасской операции, штурме Саур-Могилы, Мелитопольской, Никопольско-Криворожской, Березнеговато-Снигиревской операциях. Особо отличился во время проведения Белорусской операции.

На рассвете 24 июня 1944 г. Волошин первым из атакующих поднял свой полк в атаку, благодаря чему противник не успел воспользоваться в полной мере своей долгосрочной эшелонированной обороной. Полк прорвал ее возле деревни Гороховищи Октябрьского района Гомельской области Белорусской ССР, дав возможность расширить прорыв и ввести в него другие части. В дальнейшем полк вышел к селу Ельцы и разгромил фланг группировки противника.

26-27 июня глубоким обходом полк Волошина вышел во вражеский тыл в районе деревень Зеленковичи и Зубаревичи и разгромил немецкую группировку, захватив три батареи тяжелой артиллерии, что дало возможность дивизии 27 июня переправиться через Птичь и захватить поселок Глуск Могилевской области.

Ко 2 июля 1944 г. полк Волошина освободил 85 населенных пунктов, уничтожил около 1500 солдат и офицеров, захватил 6 танков и самоходных артиллерийских установок, 30 орудий и минометов, более 80 пулеметов, 25 складов, взял в плен более 100 солдат и офицеров противника.

Указом Президиума Верховного Совета СССР от 24 марта 1945 г. за «мужество, отвагу и героизм, проявленные в борьбе с немецкими захватчиками» гвардии подполковник Андрей Волошин был удостоен высокого звания Героя Советского Союза с вручением ордена Ленина и медали «Золотая Звезда» за номером 7259.

В дальнейшем 295-й гвардейский стрелковый полк (в том же боевом составе) продолжал вести бои по освобождению Белоруссии. Он одним из первых форсировал реку Западный Буг в районе Бреста и продолжал преследование противника на территории Польши. В сентябре 1944 г. 28-я армия была выведена в резерв и в октябре передана 3-му Белорусскому фронту, в составе которого участвовала в боях в Восточной Пруссии.

Здесь полк вновь отличился при штурме Гумбинненского укрепленного района, за что был награжден орденом Красного Знамени и получил почетное наименование «Гумбинненский». После ликвидации окруженных в районе Кенигсберга войск противника 28 армия 20 апреля была передана 1-му Украинскому фронту и в его составе участвовала в Берлинской операции. Боевые действия закончила в Чехословакии.

В 1948 г. полковник Волошин окончил Военную академию имени М.В. Фрунзе, после чего до 1959 г. преподавал в ней, затем был уволен в запас.

Был также награжден двумя орденами Красного Знамени, орденами Суворова 3-й степени и Отечественной войны 2-й степени (5 июня 1943 г.), тремя орденами Красной Звезды, а также рядом медалей.

Проживал в Москве.

Умер 24 ноября 1974 г., похоронен на Химкинском кладбище.

В честь Волошина названы улицы в поселках Глуск и Кегичевка.

Почетный гражданин Глуска с 1974 г.