There is a Jenkins plugin that let it boot instance over an API and execute the job in the freshly created instance: https://wiki.jenkins-ci.org/display/JENKINS/JClouds+Plugin
I am not sure how fast an instance will boot or whether the plugin is able to maintain a pool of VM to consume. Worth looking at though.