MySQL make two columns UNIQUE

Don't know if this is possible for MySQL because I know that it doesn't support check constraints, but what I want is to make two columns unique. Before you answer with

ALTER TABLE <table_name> ADD UNIQUE(<col1>, <col2>);

That's not what I want. I would like to ensure that col1 and col2 have unique values so if they are INTs, number "1" can exist only once between both columns, which means if col1 contains "1", col2 cannot contain "1" and "1" can only appear once in col1. Hopefully that makes sense.

I know I can do it from a php level, but right now there is a lot of code, and if I miss a spot, I don't want to destroy data integrity; I rather throw an error from the database. Some ideas that I've come across is using triggers. If someone can give me an example of using triggers to accomplish this, that would be great.

UPDATE

It might help if you knew what I was doing, then maybe you can propose a better way of doing this:

I have two fields, email and new_email. When someone changes their email address, I store it into the new_email field until the accept the change. Since email is unique because it's used as their login, I HAVE to ensure that the email is unique across both fields.