Convert clustered primary key to non-clustered and use another column for the clustered index
I don't think you can perform this operation online, since you can't just move the clustered index from one column to another, and you can't use DROP_EXISTING to reduce the amount of work that has to be done.

However, you can avoid an outage, if you're willing to perform the work. 


Create a new table with the new structure
Rename the original table, and create a view with the original name - the view will be  a union of old and new table - performance won't be fantastic but it won't be offline
Create INSTEAD OF triggers on the view to apply DML to old or new table

inserts should just go to new table
updates should try both
deletes should try both

Copy rows, in chunks, from the old table to the new table. Will need SET IDENTITY_INSERT ON and you should perform each "chunk" in its own transaction.
Once the old table contains no rows that don't exist in the new table, in a single transaction:

drop the old table
drop the view
rename the new table