To enforce unique email addresses, I would ***remove*** all competing email columns and store them in one central `email` table for all *active* emails. And another table for deleted emails:

 CREATE TABLE users (
 user_id serial PRIMARY KEY
 , username text UNIQUE NOT NULL
 , email text UNIQUE -- FK added below -- can also be NOT NULL
 );

 CREATE TABLE email (
 email text PRIMARY KEY
 , user_id int NOT NULL REFERENCES users ON DELETE CASCADE
 , UNIQUE (user_id, email) -- seems redundant, but required for FK
 );

 ALTER TABLE users ADD CONSTRAINT users_primary_email_fkey
 FOREIGN KEY (user_id, email) REFERENCES email (user_id, email);

 CREATE TABLE email_deleted (
 email_id serial PRIMARY KEY
 , email text NOT NULL -- not necessarily unique
 , user_id int NOT NULL REFERENCES users ON DELETE CASCADE
 );

This way:

- *Active* emails are unique, enforced by the PK constraint of `email`.
- Each user can have any number of active and deleted emails, but ...
- Each user can only have *one* primary email.
- Every email is always owned by one user and is deleted with the user.
- To soft-delete an email (without losing it and its affiliation to its user, move the row from `email` to `email_deleted`.
 - The primary email of a user cannot be deleted this way, because the primary email must not be deleted.
- I designed the FK constraint `users_primary_email_fkey` to span `(user_id, email)`, which seems redundant at first. But this way the primary email can only be an email that is actually owned by the same user. 
 Due to the default `MATCH SIMPLE` behavior of FK constraints, you can still enter a user without primary email, because the FK constraint is not enforced if any of the columns is null. 
 Details:
 - https://dba.stackexchange.com/questions/54387/two-column-foreign-key-constraint-only-when-third-column-is-not-null/54402#54402

The `UNIQUE` constraint on `users.email` is redundant for this solution, but it may be useful for other reasons. The automatically created index should come in handy (for instance for the last query in this answer).

The only thing that's not enforced this way is that *every* user has a primary email. You can do this, too. Add `NOT NULL` constraint to `users.email`

`UNIQUE (user_id, email)` is required for the FK constraint:

- [How does PostgreSQL enforce the UNIQUE constraint / what type of index does it use?][1]

You have doubtless spotted the **circular reference** in the above model. Contrary to what one might expect, this just works.

As long as `users.email` can be `NULL`, it's trivial:

1. `INSERT` user without email.
2. `INSERT` email referencing the owning `user_id`.
3. `UPDATE` user to set it's primary email if applicable.

It even works with `users.email` set to `NOT NULL`. You have to insert user and email at the same time though:

 WITH u AS (
 INSERT INTO users(username, email)
 VALUES ('user_foo', '[email protected]')
 RETURNING email, user_id
 )
 INSERT INTO email (email, user_id)
 SELECT email, user_id
 FROM u;

`IMMEDIATE` FK constraints (the default) are checked at the end of each statement. The above is *one* statement. That's why it works where two separate statements would fail. Detailed explanation:

- [How to deal with mutually recursive inserts][2]

To get all emails of a user as array, with the primary email first:

 SELECT u.*, e.emails
 FROM users u
 , LATERAL (
 SELECT ARRAY (
 SELECT email
 FROM email
 WHERE user_id = u.user_id
 ORDER BY (email <> u.email) -- sort primary email first
 ) AS emails
 ) e
 WHERE user_id = 1;

You could create a `VIEW` with this for ease of use. 
`LATERAL` requires Postgres 9.3. use a correlated subquery in pg 9.2:

 SELECT *, ARRAY (
 SELECT email
 FROM email
 WHERE user_id = u.user_id
 ORDER BY (email <> u.email) -- sort primary email first
 ) AS emails
 FROM users u
 WHERE user_id = 1;

To soft-delete an email:

 WITH del AS (
 DELETE FROM email
 WHERE email = '[email protected]'
 RETURNING email, user_id
 )
 INSERT INTO email_deleted (email, user_id)
 SELECT email, user_id FROM del;

To soft-delete the **primary** email of a given user:

 WITH upd AS (
 UPDATE users u
 SET email = NULL
 FROM (SELECT user_id, email FROM users WHERE user_id = 123 FOR UPDATE) old
 WHERE old.user_id = u.user_id
 AND u.user_id = 1
 RETURNING old.*
 )
 , del AS (
 DELETE FROM email
 USING upd
 WHERE email.email = upd.email
 )
 INSERT INTO email_deleted (email, user_id)
 SELECT email, user_id FROM upd;

Details:

- [Return pre-UPDATE Column Values Using SQL Only - PostgreSQL Version][3]

Quick test for all of the above: [**SQL Fiddle**][4].

 [1]: http://stackoverflow.com/a/9067108/939860
 [2]: http://stackoverflow.com/a/24816197/939860
 [3]: http://stackoverflow.com/a/7927957/939860
 [4]: http://sqlfiddle.com/#!15/b2c90/6