Add a primary key constraint to an existing unique column
The assumption you have is that a lock will occur when creating a new table. This is false if you use the correct query hints &amp; have a good action plan. I recommend the following:


Create a New table with identical schema but with a primary key constraint added.
INSERT INTO NewTable SELECT * FROM OldTable (this will still take a while)
Use SSIS or write a good function to identify new rows in the old table whilst the insert into the newtable was occuring and write these rows to the new table. (Essentially perform another merge ontop)
Rename/Drop the old table and rename the new table to the old table name.


On the topic of locks. You have a few options as I see:


Specify NOLOCKS or READUNCOMITTED on your query. This has its own implications that are best read here.
Take a full table lock which you've already said is less desirable but would mean step 3 of the action plan is not required.
Take shared page locks (Default for select). This means that the individual pages when being read will lock and no updates or inserts will be allowed. It does mean though that other selects on this page can still occur during this lock. 


It really depends on your specific need which of these three is your best COA. I suggest consulting with business to determine if an outage is really such a bad thing and if it is, consult with the developers to determine what lock level is most appropriate for the task.