Restartability is not possible with a multi-threaded step, because threads can (and will) override each others state in the execution context. That's why the javadoc of stateful readers mentions to disable state management in multi-threaded steps. Here is an excerpt from the JdbcPagingItemReader:
The implementation is thread-safe in between calls to open(ExecutionContext),
but remember to use saveState=false if used in a multi-threaded client
(no restart available)
Same mention in the Javadoc of JpaPagingItemReader and others. The process indicator pattern is the way to go, but you said you can't add the column in your table..
What you can probably try is create a temporary table with the required data + column (in a first step) and remove it (in a final step) once the job is successfully executed. The lifecycle of the temporary table will be the same as the job instance (ie it can survive a job execution failure and be available for the next run). The successful job execution would remove it (this can be done automatically in a final step of the job to avoid manual house-keeping of temporary tables in your db).