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: GCD-Domains.
See also Pete's response to “Counter”-example for Gauss’s Lemma on irreducible polynomials.