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,
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.