I'd use something like the following:

# pseudocode
while (1) {
   acquire_lock();   # blocks
   choose_record();  # choose an unflagged record
   flag_record();    # this one is mine
   release_lock();   # let others in 
   process_record(); # do work
}
[download]

MySQL has "advisory" locking that is suitable for this (see MySQL functions GET_LOCK() and RELEASE_LOCK()).