Родился в г. Актюбинске Казахской ССР. В 1973 О. И. Гайданов окончил Всесоюзный юридический заочный институт и получил диплом юриста.
Еще до окончания учебы, в 1971, стал работать в органах прокуратуры, первое время помощником прокурора г. Актюбинска, а затем на аналогичной должности в прокуратуре Актюбинской области. В 1974 О. И. Гайданов был выдвинут на должность прокурора Пролетарского района г. Актюбинска. В 1978 направлен на работу в Гурьевскую область, где стал вначале заместителем, а впоследствии — первым заместителем прокурора области. С 1981 — заместитель начальника следственного управления, член коллегии Прокуратуры Казахской ССР.
В 1983 О. И. Гайданов защитил диссертацию на соискание ученой степени кандидата юридических наук. В октябре 1984. приказом Генерального прокурора СССР назначен заместителем прокурора Узбекской ССР и утвержден членом коллегии Прокуратуры республики. В 1989 О. И. Гайданов был назначен прокурором Целиноградской области (впоследствии переименована в Актюбинскую область). После распада Советского Союза, переехал на постоянное место жительства в Россию. Работал заместителем прокурора войсковой части. В феврале 1994 назначен начальником следственного управления Генеральной прокуратуры Российской Федерации, а в мае того же года — заместителем Генерального прокурора. С 11 октября 1995 временно исполнял обязанности Генерального прокурора Российской Федерации. В ноябре 1995 освобожден от должности заместителя Генерального прокурора, а в январе 1996 уволен из органов прокуратуры на пенсию.
Какие-либо заметные деяния, которые бы обогатили историю Российской прокуратуры за тот непродолжительный период пребывания в должности главного законника страны, Гайданову осуществить не удалось. А планы такие были, и он автору о них рассказывал. Все, что успел Гайданов, — это прекратить пресловутое дело по «Куклам».