What is proper database design for a drupal table with an order field?
The problem is similar to this (SO) question:
How to swap values of two rows in mysql without violating unique constraint?

Unfortunately, the answer is the same. Due to how MySQL checks UNIQUE (and primary and foreign key) constraints, i.e. row by row and not at the end of statements or at the end of transactions, swapping or rearranging values that are part of unique constraints, cannot be done easily.

I would go with your 1st suggestion:

1. Update each row's order with some large number (i.e. 1001, 1002, 1003) so that the original order is no longer conflicting, then update each row with the correct order values (1, 2, 3). 

This way you can have the minimal (2) statements required to do the update and any other connection that reads the table between the 2 statements will still read a consistent state of values.