use standard ETL tools
As a starter, the question illustrates the need for good design up front. You are now in "always time to do it over, never time to do it right" mode.
There are several ways to handle this, it seems to me - none of them pretty. You will need to extract the data out to a holding table, drop and re-create the existing table with the constraint then attempt to insert each new row. If the insert fails you need to catch the exception. You can then do one of several things. First, you can try getting a valid postal code from any one of a number of commercially available applications - this will probably still leave some invalid zips as none of these systems are 100% accurate; second you can try to resolve this by hand, having a business person go through each line; third, you can just dump the bad records and hope your customers come back.
You should also hire someone who understands DB design.
