Sounds like you want to just use Thread::Queue objects inside a Thread::Queue, dequeue from the parent, then work on the child. A potential problem with this is that you can't modify the child queue in place (except by peeking) and would potentially have to keep a reference to it separate from the parent queue.

Alternatively you could use an actual state machine implementation from CPAN.