How about the "good old" 80/20 rule? Those 500,000 rows, are they more or less than 20% of the totoal number of rows in the table?
If more
THEN EXPORT in a seq.file, update the records in the seq.file and reload the file into the table (db must be quiesced)
ELSE just code and execute the UPDATE query(s). See if you can divide the set into logical chunks and include that logic in you where clause. This will take the pressure off the log bottleneck.