Почему же, получается, что степень должна быть неограниченно большой, и в итоге я имею не конечное декартово произведение, а счетное.
Не произведение, потому что у каждого многочлена только конечное количество ненулевых коэффициентов. Многочленов 0-й степени счётное число, 1-й -- счётное, 2-й -- счётное... Итого счётное объединение счётных. (Произведение было бы, если бы вместо многочленов рассматривать формальные степенные ряды, там нет ограничения на количество ненулевых коэффициентов.)
Про сепарабельность: на любом множестве можно ввести дискретную метрику (расстояние между любыми 2 различными элементами
).