Parece que você precisa de algum tipo de marcador para identificar linhas como "em uso" para que as outras instâncias não processem os mesmos dados; se você usa um tipo booleano ou data é irrelevante, de alguma forma você deve marcar as linhas em uso.

Você pode fazer isso por meio de um dispatcher, um processo ou thread com acesso exclusivo à sua tabela e o único trabalho é selecionar linhas e passá-las para outros processos para trabalhar. Mesmo assim, o despachante terá que saber até onde os dados chegaram para que você volte ao mesmo problema.

Outra maneira é usar um campo para indicar que a linha está em uso (como você disse em sua pergunta). Cada processo atualiza um bloco de linhas com um ID único, realizado dentro de uma transação para travar a tabela; Eu usaria o número de conexão retornado de CONNECTION_ID() para marcá-los, então você sabe que é único.

Após o UPDATE ... WHERE connection_id IS NULL (com um limite aplicado) a transação está completa o processo pode SELECT ... WHERE connection_id = CONNECTION_ID() para obter suas linhas para processamento.

Quando eles completam seu trabalho, todo o ciclo começa novamente para marcar o próximo conjunto de linhas até que todas tenham sido processadas.