Uniqueness constraint for elements of arrays in the entire table
Yes, as you said, I'd create an emails table that refer to the users.
CREATE TABLE users (
    id_user         ... ,
    username        varchar(255),
    ... ,
    PRIMARY KEY(id_user)
);

CREATE TABLE emails (
    id_email        ... ,
    id_user         ... ,
    email           varchar(255),
    ...,
    PRIMARY KEY(id_email),
    CONSTRAINT fk_user
      FOREIGN KEY(id_user) 
      REFERENCES users(id_user)
);

Then in the emails table you can add a unique constraint on id_user, id_email.
CREATE UNIQUE INDEX CONCURRENTLY xak1_unique_id_user_and_email_ix
ON emails (id_user, id_email);

ALTER TABLE emails ADD CONSTRAINT xak1_unique_id_user_and_email UNIQUE
                      USING INDEX xak1_unique_id_user_and_email_ix;

P.S. I don't work usually on PostgreSQL, for the syntax I referred to link