Родился 21 марта 1972 г. в Астрахани в семье инженеров.
В 1994 г. окончил исторический факультет Астраханского государственного педагогического института им. С. М. Кирова (ныне - Астраханский государственный университет), в 2002 г. - Санкт-Петербургский государственный университет по специальности "правоведение", в 2015 г. - Астраханский государственный технический университет по специальности "юриспруденция".
В 1991 г. был избран в координационный совет Объединенного фронта трудящихся (ОФТ), с 1992 г. - член исполкома ОФТ. Фронт был образован членами КПСС, находившимися в оппозиции президенту СССР Михаилу Горбачеву и недовольными "попытками дискредитировать марксизм-ленинизм". Позднее на его базе были созданы Российская коммунистическая рабочая партия Виктора Тюлькина и движение "Трудовая Россия" Виктора Анпилова.
В 1994-1995 гг. работал учителем истории в школе села Три Протока Приволжского района Астраханской области.
В 1994-1997 гг. – депутат Астраханского областного представительного собрания (впоследствии - Дума Астраханской области) I созыва. Был избран 9 октября 1994 г. от регионального отделения ОФТ. Являлся заместителем председателя комитета областного парламента по природопользованию и природным ресурсам.
С 1995 г. участвовал в деятельности Объединения рабочих профсоюзов "Защита", в 1996 г. был избран сопредседателем его астраханской организации. С 1997 г. - сопредседатель межрегионального объединения рабочих профсоюзов "Защита труда" вместе со Львом Гамовым и Владимиром Лапшиным.
17 декабря 1995 г. баллотировался в Государственную думу РФ II созыва по списку избирательного блока "Коммунисты - Трудовая Россия - За Советский Союз" (№12 в центральной части списка). По итогам голосования блок не преодолел 5-процентный барьер. Олег Шеин также выдвигался по Астраханскому одномандатному округу №62, где занял седьмое место из 17, набрав 4,63% голосов. В Думу не прошел.
В 1997-1999 гг. - депутат Астраханского областного представительного собрания II созыва. Был выдвинут избирательным объединением "Астраханская организация Объединенного фронта трудящихся России". Набрал 33,9% голосов. В Собрании занимал пост председателя комитета по законности, правопорядку, нормотворчеству и местному самоуправлению. 28 декабря 1999 г. депутатские полномочия были досрочно прекращены в связи с избранием в Государственную думу РФ.
Был одним из организаторов ряда рабочих забастовок и кампании против введения в Астрахани повременной оплаты телефонной связи.
В 1999-2003 гг. – депутат Госдумы РФ III созыва. 19 декабря 1999 г. избран по Астраханскому одномандатному округу №61, набрал 21,47% (ближайший соперник – кандидат от КПРФ Николай Арефьев - 19,07%). В Думе входил в состав депутатской группы "Регионы России", был членом комитета Госдумы по труду и социальной политике, также входил в межфракционную депутатскую группу по взаимодействию с рабочим и профсоюзным движением "Солидарность".
В 1999-2002 гг. - член исполкома Движения за Рабочую партию.
В 2002-2003 гг. возглавлял Российскую партию труда (председателем федерального совета партии был лидер профсоюзного объединения "Соцпроф" Сергей Храмов).
28 мая 2002 г. был одним из организаторов несанкционированного выступления антиглобалистов на Пушкинской площади в Москве, которое было разогнано ОМОНом.
В 2003-2007 гг. – депутат Госдумы РФ IV созыва. 7 декабря 2003 г. избран по Астраханскому одномандатному округу №63, набрал 35,85% (ближайший соперник – депутат Астраханской Думы Сергей Боженов – 22,68%). Самовыдвиженец, на выборах был поддержан избирательным блоком "Родина". В Думе входил в состав фракции "Родина", являлся заместителем председателя комитета по труду и социальной политике.
С 2005 г. член политсовета партии "Родина". В 2006 г. в результате объединения "Родины" с Российской партией жизни и Российской партией пенсионеров была образована партия "Справедливая Россия: Родина/Пенсионеры/Жизнь" (с 2009 г. - "Справедливая Россия").
В 2006 г. вошел в состав президиума центрального совета "Справедливой России" (с 2021 г. - "Справедливая Россия - Патриоты - За правду").
В 2007-2011 гг. – депутат Госдумы РФ V созыва. 2 декабря 2007 г. избран по списку партии "Справедливая Россия: Родина/Пенсионеры/Жизнь", возглавлял список в региональной группе №35 (Республика Калмыкия, Астраханская область). В Думе занимал пост заместителя председателя фракции "Справедливая Россия: Родина/Пенсионеры/Жизнь", также был заместителем председателя комитета по труду и социальной политике.
11 октября 2009 г. баллотировался на пост мэра Астрахани от партии "Родина". По итогам голосования занял второе место (26,03%). Выборы выиграл действующий мэр города Сергей Боженов (65,56%). 12 октября 2009 г. Олег Шеин заявил, что победа Боженова стала возможной лишь в результате масштабных фальсификаций, и потребовал отмены итогов выборов. Его сторонниками был выстроен палаточный городок, который был разобран милицией 13 октября.
4 декабря 2011 г. на выборах в Госдуму РФ VI созыва возглавлял список региональной группы №30 (Республика Калмыкия, Астраханская область), выдвинутый партией "Справедливая Россия". По итогам голосования в Думу не прошел.
В 2011-2016 гг. депутат Думы Астраханской области V созыва. Был избран 4 декабря 2011 г. по списку регионального отделения "Справедливой России". Являлся руководителем партийной фракции в Думе, входил в состав комитетов по государственному строительству, законности и правопорядку и по строительству и жилищно-коммунальному хозяйству.
4 марта 2012 г. баллотировался на пост мэра Астрахани от регионального отделения "Справедливой России". По данным избиркома, занял второе место, набрав 29,96% голосов избирателей. Мэром Астрахани был объявлен действующий вице-мэр города, кандидат от "Единой России" Михаил Столяров, набравший 60%. Олег Шеин не признал итоги выборов и вместе с рядом астраханских депутатов-эсеров объявил голодовку, которая продолжалась с 16 марта по 24 апреля. Он также направил исковое заявление в суд с требованием отмены результатов голосования. В апреле поддержать голодающих в Астрахань приезжали председатель "Справедливой России" Сергей Миронов, оппозиционные политики Алексей Навальный, Илья Яшин и др. 11 апреля во время отчета премьер-министра РФ Дмитрия Медведева в Госдуме большая часть депутатов "Справедливой России" покинула зал заседаний в знак солидарности с Олегом Шеиным. 19 апреля 2012 г. председатель Центризбиркома Владимир Чуров признал факт нарушений на 138 из 202 избирательных участках Астрахани. При этом он заявил, что они носили процедурный характер и не могли повлиять на результаты голосования. 15 июня 2012 г. Кировский районный суд Астрахани отказал Олегу Шеину в удовлетворении его требований.
22 октября 2012 г. был избран в Координационный совет российской оппозиции (КСО) по общегражданскому списку. Покинул КСО в январе 2013 г. после того, как президиум бюро "Справедливой России" потребовал от членов партии прекратить деятельность в рядах несистемной оппозиции.
21 ноября 2013 г. Олег Шеин был доставлен с тремя ножевыми ранениями в Институт скорой помощи им. Склифосовского. Нападение на него в одном из московских хостелов совершила студентка из Магнитогорска Татьяна Павлова. Следствием было установлено, что Павлова пыталась ударить ножом своего знакомого, а Шеин пытался ее обезоружить и в результате был ранен. Нападавшую суд признал невменяемой и направил на принудительное лечение.
14 сентября 2014 г. Олег Шеин участвовал в выборах губернатора Астраханской области (выдвинут местным региональным отделением "Справедливой России"). Занял второе место с результатом 16,22%. Победу одержал действующий глава области Александр Жилкин (75,28%).
13 сентября 2015 г. был избран в городскую думу Астрахани (возглавлял партийный список "Справедливой России"). После выборов отказался от депутатского мандата.
В апреле - октябре 2016 г. являлся депутатом Государственной думы РФ VI созыва. 13 апреля 2016 г. Олегу Шеину был передан депутатский мандат лидера "Справедливой России" Николая Левичева, который перешел на работу в Центризбирком. В Думе Шеин вошел в комитет по жилищной политике и жилищно-коммунальному хозяйству.
18 сентября 2016 г. избран депутатом Государственной думы РФ VII созыва по списку "Справедливой России", был первым номером в региональной группе №6 (Республика Калмыкия, Астраханская область, Калининградская область). Также баллотировался по Астраханскому одномандатному округу №74, где с результатом 32,95% проиграл выборы единороссу Леониду Огулю (38,74%). Заместитель руководителя фракции "Справедливая Россия".
1 июля 2019 г. подал в избирательную комиссию Астраханской области документы для участия в выборах губернатора региона 8 сентября (путем самовыдвижения). Однако не смог пройти муниципальный фильтр, поэтому не был зарегистрирован избиркомом в качестве кандидата на пост главы области.
19 сентября 2021 г. участвовал в выборах депутатов Государственной думы РФ VIII созыва по федеральному списку партии "Справедливая Россия - Патриоты - За правду". Баллотировался под первым номером региональной группы №9 (Республика Калмыкия, Астраханская, Волгоградская обл.). По итогам распределения мандатов место в новом созыве Госдумы не получил. Кроме того, был выдвинут партией по Астраханскому одномандатному избирательному округу №74. Уступил кандидату от "Единой России" Леониду Огулю с результатом 19,2% голосов.
С сентября 2021 г. - депутат Астраханской областной думы VII созыва. Был избран в облдуму 19 сентября 2021 г. по списку партии "Справедливая Россия - Патриоты - За правду". С сентября 2021 г. по сентябрь 2023 г. - руководитель фракции "Справедливая Россия - За правду" в Астраханской областной думе.
Был секретарем президиума партии "Справедливая Россия" (с 2021 г. - "Справедливая Россия - Патриоты - За правду") по вопросам социальной политики. До 2023 г. возглавлял совет астраханского регионального отделения партии.
Имеет благодарность правительства РФ (2019).
Автор книг "Неизвестный фронт Великой Отечественной: кровавая баня в калмыцких степях" (2009), "Разгром грузинских захватчиков под Цхинвали" (2009), "Как отстоять свой дом без оружия? Практические рекомендации по жилищному самоуправлению" (2013).