You could use a combination of the Views, Rules and Views Rules modules to get this to work. Some details about the Views Rules module (from its project page):
Provides Views directly as Rules actions and loops to seamlessly use view result data.
If you're not familiar with Rules (yet), the previous quote may seem a bit cryptic (it may make you think like "so what, how can this help me?"). Therefor some more details about how to move forward using these modules:
- Create a view (using Views) so that you have (at max) 1 Views result (row) for each of your nodes contained in your "queue to be published" (as in your question), whereas that view has just a few fields (columns) that you'll need later on to publish it (possibly only the node id is all you'd need). Important: use a Views display type of "Rules", which you can do if you have Views Rules enabled. Refer to my answer to "How to create a rule which after several updates in 5 minutes of a node sends 1 message?" for way more details about creating such Views display.
- Create a custom rule in which you use the Views Rules module to iterate over each of these Views results in a Rules action, using the Rules technique known as a "Rules Loop". If you limit the Views result to only 1, this iteration is also limited to 1 of course (which is what you want).
- For each iteration step in your Rules loop (there should only be 1 in your case ...), perform a Rules Action to simply publish the node being processed. At that point you'll have all data from each column of your Views results available as so called Rules Parameters. But in your case you probably only need the node's ID.
- The only remaining thing is to decide about the Rules Event to use for this rule to be triggered. Obvious, in your case you should use Rules Event Cron maintenance tasks are performed.
With the above in place, the only thing left is to decide about the "set interval" (as in your question). For that, all that's needed is to review the scheduling of your cron jobs: each time cron runs, there will be 1 such node that gets published (provided there is one at least at the moment cron runs).
Easy, no?