Consider creating a new table with the same schema plus the rowversion column, and add a view atop both tables that does a union all. Have people use the view, and write instead-of triggers against the underlying tables & views.
Inserts should be sent to the new table, updates should move data to the new table, and deletes should be applied to both tables.
Then do batch moves in the background, moving as many records at a time as you can over to the new table. You can still have concurrency issues while this is going on, and some craptacular execution plans, but it lets you stay online while the moves are happening.
Ideally, you start the process on a Friday afternoon to minimize the effect on end users, and try to get it done before Monday morning. Once it's in place, you can change the view to point to just the new table, and the craptacular execution plans go away. Ideally.
To avoid the triggers firing when the data is being migrated in batches, look at the number of rows in the deleted/inserted tables in the trigger, and skip the activities if they're near to the number of rows in your batch.
In the finish, Michael decided to skip the view (and not delete from the original table) to get more stable plans. The trade off was holding essentially two copies of the table. He turned it into a series of blog posts.