Немного информации не хватает. Дедушка до войны жил в Омске, и известно, кто были его родители, значит, надо понять, где эти родители жили.
Даже если дедушка до войны был ребенком, то его родители родились ближе к рубежу веков - это уже надо искать не в ЗАГСе, а в архивах.
Если родители тоже из Омска, то придется искать метрические записи церквей этого города. Если не известно, откуда они родом, то тут много вариантов. Расскажите нам подробнее, мы придумаем, что делать.