Since Charles has already given you an example, I'll just mention that there is a name for integral domains in which any two non-zero elements have a gcd: <a href="http://en.wikipedia.org/wiki/GCD_domain">GCD-Domains</a>.

See also Pete's response to <a href="https://mathoverflow.net/questions/6651/counter-example-for-gausss-lemma-on-irreducible-polynomials">“Counter”-example for Gauss’s Lemma on irreducible polynomials</a>.