If the table is is 3NF, then that unique constraint across all keys holds.

I don't think that's quite true. Consider this simple example:

CREATE TABLE supplier (
  id SERIAL PRIMARY KEY,
  name TEXT
);

INSERT INTO supplier (name) VALUES ('Apple');     -- Computer
INSERT INTO supplier (name) VALUES ('Microsoft');
INSERT INTO supplier (name) VALUES ('Apple');     -- Records

SELECT * FROM supplier;
 id |   name    
----+-----------
  1 | Apple
  2 | Microsoft
  3 | Apple

This table is in the third normal form, in so far as I understand it, because "none of the non-primary key attributes is a fact about any other non-primary key attribute". However, you'll notice that there is a duplicate, in that "Apple" is listed twice. That's because there are two different companies named "Apple". So this table is technically in 3NF, but you cannot have a unique index across all of its columns.

That's not to say that this is a good example, or that you couldn't work around this issue in various ways, but it demonstrates, I hope, that 3NF does not mandate that all columns be unique.

—Theory