Is there a ring for which the reducibility of a polynomial is undecidable? Let $R$ be a ring such that all of its elements have a finite number of divisors, ie $\forall r\in R\, |\{x\in R: x|r\}|<\infty$.
Then we can decide whether a polynomial in $R[t]$ is reducible through Kronecker's method.
Even in the ring $\mathbb{Q}[x,\sqrt{x},\sqrt[4]{x},...]$, where $x$ has an infinite number of divisors, it is easy to list any polynomial's possible factors, and reducibility is decidable.
Is there a ring for which the reducibility of a polynomial is undecidable?
Is there a countable ring with computable ring operations and decidable equality for which the reducibility of a polynomial is undecidable?
 A: Yes, but the answer is a bit unsatisfying. This answer is a summary of the very nice paper Computable Fields and Galois Theory, Russel Miller, Notices of the AMS, 2008.
First of all, if one could not even compute with the elements of the ring $R$ at all, it would be unclear what it would mean for factorization to be computable. The usual solution is to talk about "computable rings", meaning a countable (or finite) ring $R$ where the elements are indexed by integers and the operations of addition and multiplication are given by computable functions.
The following is an example of a computable field in which factorization is not decidable: Let $p_n$ be the $n$-th prime and let $T_n$ be the $n$-th Turing machine and let $K = \mathbb{Q}(\sqrt{p_n} \ : \ T_n \ \mbox{halts})$. Given any element $\theta$ of $K$, there is a finite expression which witnesses that $\theta$ is in $K$: namely, the algebraic expression for $\theta$ in terms of finitely many $p_n$'s and a transcript of the ruunning of the corresponding Turing machines. This can be made into a proof that $K$ is computable, in particular (in response to Matt F.'s comment) there is no issue with testing equality. However, $x^2 - p_n$ is reducible iff $T_n$ halts, so we cannot test reducibility.
The fields one normally meets in life do not have this issue. Reducibility is computable over $\mathbb{Q}$, $\mathbb{R} \cap \mathbb{Q}^{\mathrm{alg}}$ and over finite fields. If reducibility is computable over $k$, then it is computable over $k(t)$ and over $k[t]/f(t)$ for $f$ irreducible. That already covers the most obvious fields you know.
Searching for "computable fields" turns up a fair bit of recent research.
