Una posible solución es simplemente usar DROP IF EXISTS antes de crear la nueva restricción.
ALTER TABLE foo DROP CONSTRAINT IF EXISTS bar;
ALTER TABLE foo ADD CONSTRAINT bar ...;
Parece más fácil que intentar consultar esquemas de información o catálogos, pero puede ser lento en tablas grandes, ya que siempre recrea la restricción.
Editar 2015-07-13:Kev señaló en su respuesta que mi solución crea una ventana corta cuando la restricción no existe y no se aplica. Si bien esto es cierto, puede evitar esa ventana con bastante facilidad al incluir ambas declaraciones en una transacción.
