Is SELECT FOR ... UPDATE *necessary* to DELETE or UPDATE multiple rows without deadlock?
Your assessment is spot on, and there is no better way of doing it.

As an alternative, you could do without the sort, but delete in smaller batches, each in its own transaction. That is still susceptible to deadlock, but the likelihood is smaller, and re-running the transaction doesn't hurt quite as much.