We built our own .deb containing all our bits, that depends on external dependencies. The .deb recipe is checked into source. Our deploy process is
1) compile the .deb.
2) spawn a new, empty EC2
3) apt-get the .deb
4) lein daemon start (http://github.com/arohner/lein-daemon)