Como posso gerar uma string exclusiva por registro em uma tabela no Postgres?

Não afirmo que o seguinte seja eficiente, mas é como fizemos esse tipo de coisa no passado.

CREATE FUNCTION make_uid() RETURNS text AS $$
DECLARE
    new_uid text;
    done bool;
BEGIN
    done := false;
    WHILE NOT done LOOP
        new_uid := md5(''||now()::text||random()::text);
        done := NOT exists(SELECT 1 FROM my_table WHERE uid=new_uid);
    END LOOP;
    RETURN new_uid;
END;
$$ LANGUAGE PLPGSQL VOLATILE;

make_uid() pode ser usado como padrão para uma coluna em my_table . Algo como:

ALTER TABLE my_table ADD COLUMN uid text NOT NULL DEFAULT make_uid();

md5(''||now()::text||random()::text) pode ser ajustado a gosto. Você pode considerar encode(...,'base64') exceto que alguns dos caracteres usados na base-64 não são compatíveis com URL.