I don't think it's really that impossible. Yes, there are some kind of SELECTs that either don't make sense, or are almost certainly not what the user wants, or are impossible to do.
But trying to use a very specialized engine for general purpose queries is not really something to worry about.
I would take the same approach that I do with my S3 storage engine, e.g., implement whatever makes sense, and then for the cases were it doesn't make sense, tell the user "So, don't do that, then!".
For a queue engine, I would separate the operations of "get next item" and "delete"
SELECT id,message FROM queue LIMIT 1;
DELETE FROM queue WHERE id="foo";
But then, I've been thinking about how to wrap the Amazon AWS SQS service up as a storage engine, and this approach fits with SQS reasonably well.