Painless way to create a clustered index on a huge table?

So we have a customer site that is complaining about some seriously slow performance. I took one look and it's obvious that the problem is because Somebody Else (grrrr) designed a table holding some 20 million-plus records without a clustered index.

Now I want to create a clustered index on that table - but in my test environment my create index command has been running for an hour and it's still not done. The customer site is a shop floor that works 24/7, and cannot afford an hour of down time while I create an index.

Is there some less brute-force method of creating the index that will either finish the job quickly, or do it in some smart way that will not totally kill the server's performance while it's busy?

We are using SQL Server Enterprise Edition.

-
If your sql server is Enterprise+ edition and table has no any BLOB fields - CREATE CLUSTERED INDEX ... WITH(ONLINE=ON)

-
If not - there is no any way except to create the table with the same schema on side and wisely transfer data to it, including all INSERT/UPDATE/DELETE operations (using trigger, for example), and then accurately drop old table and rename new to the same name as old - cons are: slow, adds extra load to server and storage

StackExchange Database Administrators Q#11956, answer score: 26