Rebuild Very Large Primary Key Index I have a SQL database that is hosted on Azure. The problem is that the size is getting out of control, I can see up to 99% fragmentation in the Primary Key clustered indexes.

I'm able to rebuild all other indexes with online=on option and it won't affect performance. The size of one of the PK Clustered indexes is greater than 200GB, and for this one a REBUILD...WITH (ONLINE=ON) causes locking.

We do have users from all timezones accessing the site so really, I'm unable to find a time where I can rebuild the index offline.

What is the best strategy to rebuild large indexes without having a downtime in the site?

I believe reorganize won't help since fragmentation is 99%. The problem is that the table gets locked even with online. The main problem is that the index is greater than 200GB. The primary key is an integer.
Even though it's a bit late, I'm going to field a response with hope that it helps or at least spurns some additional ideas/commentary on this issue because I think it's a good question.

First, and I don't know if you're doing this or not, but please don't assume that high fragmentation levels on the index are always going to cause poor performance.  Stale statistics (e.g. sys.dm_db_stats_properties) and high amounts of white space per page (i.e. avg_page_space_used_in_percent column in sys.dm_db_index_physical_stats dmv) hold more relevance regarding performance issues than fragmentation alone.  Yes, highly fragmented indexes will generate more read-aheads and you typically do see stale statistics and higher levels of white space per page coupled with fragmentation, but fragmentation isn't directly tied to query plan optimizations nor how much memory loading the index from disk will actually consume.  Query plans are affected by statistics and your memory footprint bloats with more white space.  For instance, an index that is 99% fragmented but has less than 5% avg. white space and up-to-date statistics is likely not causing you drastic performance issues as compared to either a bad execution plan as a result of stale statistics or constant paging of an index that's too big to fully fit in memory because there's a significant amount of white space present per page.

If fragmentation is truly an issue, you can reduce it, ONLINE, by issuing an ALTER INDEX ... REORGANIZE statement as identified by Dan Guzman in the comments.  This won't create as streamlined an index as a REBUILD operation will, but it will reduce your fragmentation.  The key here is to identify windows of lower usage on your database and run it then.  This could be 15 minutes or multiple hours, obviously the longer the better, but the key here is this operation doesn't rollback and retains any progress made even if you kill it mid-execution.

If, in a perfect world where your fragmentation was eliminated, would it make more sense to utilize partitioning on this table?  Azure SQL Database does allow for table partitioning and Microsoft has a great article outlining some Partitioning strategies for Azure SQL Database.  If your data is non-volitile, partitioning it may help reduce maintenance needs, and if coupled with Table Compression, you may even be able to reduce your overall storage footprint as well.  Alberto Murillo's earlier answer alludes to utilizing Horizontal Partitioning based on a data region, and this approach may help create some maintenance windows for you as your data would be more regionally specific instead of global.

Transitioning to a partitioned table won't be easy with your current absence of maintenance windows, but you may be able to utilize an approach outlined by Maria Zakourdaev which uses Partitioned Views over the top of your current table and a new partitioned table to start partitioning future data.  As time goes on (and hopefully your old data is purged), you can eventually transition fully over to the partitioned table.  Again, I don't know your data or application, but maybe this approach is something you can employ.