Родился 5 января 1970 года в городе Ревда. Начинал карьеру в футбольной секции ДЮСШ «Юность» в Ревде у тренера Валерия Соколова. Играл с командой на турнирах «Кожаный мяч», где его заметили селекционеры «Уралмаша».
В 6-м классе перешёл в ДЮСШ «Уралмаш», где занимался у известного в 1970-е уральского футболиста Валерия Войтенко. За основу «Уралмаша» дебютировал в 1986 в матче против «Светотехники». С 1988 — твердый игрок основы. Сначала играл на позиции левого полузащитника, с конца 1988 — на позиции опорного.
Когда наступил призывной возраст, перешёл в областную команду МЦОП (базировалась в пригороде СвердловскаВерхней Пышме). В одном из матчей на него обратили внимание селекционеры ЦСКА и взяли в команду «Чайка-ЦСКА» (фарм-клуб армейцев; играла в 1-й зоне 2-й лиги). Сам Веретенников переезжать в Москву не хотел, поэтому после неудачно проведённого матча на Кубок СССР против саратовского «Сокола» самовольно уехал обратно в Свердловск. Тем не менее руководство «Уралмаша» уговорило футболиста вернуться в армейский клуб. После 8 игр, проведённых Веретенниковым, в клуб пришла директива командировать его и ещё несколько человек на усиление клуба СКА Ростов-на-Дону, игравшего в 1-й лиге. Всё это время Веретенникова продолжали звать в ЦСКА, но никаких гарантий не давали.
В итоге сезон 1991 года он начал в составе «Уралмаша», новичка 1-й лиги. Он заключил годовой контракт с клубом, одним из условий соглашения было предоставление квартиры. Предоставив квартиру, клуб рассчитывал, что это обяжет Веретенникова остаться ещё на некоторое время в Екатеринбурге, но у него были иные планы. В 1992 году, при помощи президента «Ротора» Владимира Горюнова, Веретенников переехал в Волгоград. Именно в составе «Ротора» он провёл свои лучшие годы: на его счету немало командных и личных достижений за семь лет выступлений в клубе (1992—1999). Например, во втором туре чемпионата России-98 Веретенников забил 5 голов в ворота «Шинника». За эту игру он получил от газеты «Спорт-Экспресс» 9,5 балла из 10 возможных.
В 2000 году уехал в Грецию, где недолго играл за «Арис» (Салоники), затем выступал за бельгийский «Льерс», также не слишком успешно; в итоге сделать карьеру за рубежом ему не удалось.
После возвращения из «Льерса» играл в саратовском «Соколе». После вылета клуба из Премьер-лиги играл в различных клубах Первого дивизиона, затем в Высшей лиге Казахстана. Попытки вернуться в «Ротор» закончились успехом только в 2005 году, который этот клуб начал во Второй лиге. По итогам сезона Олег стал лучшим игроком зоны «Юг»[4]. Однако в следующем году, не найдя взаимопонимания с президентом Горюновым, вынужден был покинуть «Ротор» и снова отправиться в Казахстан, где играл ещё два сезона.
С февраля 2010 года являлся помощником главного тренера «Ротора»[7]. В декабре 2010 года окончил Высшую школу тренеров с присвоением категории Б[8]. 11 июня 2014 года стал главным тренером команды[9]. Был на своём посту до весны 2015 года[10]. 17 июня 2015 года возглавил «Луч-Энергию»[11]. Ушёл в отставку в октябре.
Сезон 2016/17 проработал главным тренером молодёжной команды «Оренбурга». В июле 2017 года вошёл в тренерский штаб Роберта Евдокимова в костанайском «Тоболе»[12].
В декабре 2017 года закончился контракт с «Тоболом»[13].
15 октября 2018 года, по инициативе Роберта Евдокимова[14] вернулся в волгоградский «Ротор» в качестве тренера-селекционера[15]. В 2019 году являлся главным тренером «Ротора-2».
С 2020 по 2022 год входил в тренерский штаб ФК «Рубин» (Казань).
Старший брат (на 12 лет) — мастер спорта по лыжным гонкам. Также есть сестра Ольга.
Жена — Лариса (поженились в 19 лет), сын Павел (род. 8 июня 1991), дочь Татьяна (род. 7 января 1997). Павел также стал профессиональным футболистом, выступал за «Волгоград», «Ротор» и «Энергию».
29 октября 1998 года, за день до окончания чемпионата России, на волжской набережной неизвестный напал на Веретенникова, который прогуливался с дочерью, и плеснул в игрока кислотой. Ядовитая жидкость попала и на лицо Тани: отец смыл с лица девочки кислоту и доставил её в больницу. Несмотря на случившееся, Веретенников сыграл в заключительном туре против «Торпедо», выйдя под овации зрителей во втором тайме. Предложения о помощи семье Веретенникова поступали со всей России и из-за границы, а вскоре врачи из Волгограда сообщили, что здоровью девочки ничего не угрожало. 20 декабря в присутствии двух понятых Веретенников опознал на одном из фото нападавшего: им оказался житель Казахстана, у которого в Волгограде были родственники[20].