В варианте с базой данных тогда неплохо бы еще добавить колонку "ts", куда писать таймстамп.
И в запросе забирать проксю примерно так:
SELECT * FROM proxies WHERE work=1 ORDER BY ts ASC LIMIT 1
При взятии соотвественно обновлять таймстамп и work=1.
И блокировку транзакции надо не забыть сделать, чтобы одновременно разные потоки не забирали одну проксю.