Deploy our own software using Puppet?

We use puppet, but we don't use it for our application deployments. As you said, you could package your software into debs or rpms, configure your private repository everywhere, and use puppet to control versions, but you're still at the mercy of waiting for the next 30 minute refresh on all your servers.

What I would do (and this is close to what we do, but we use rails so there's no compile step):

• Use puppet to configure everything on the server except the application itself. Dependencies, web servers, users, paths, etc.
• Have your automated build server (bamboo, hudson, cruise control, etc.) put the compiled artefacts in a repository manager like Nexus.
• Use capistrano to push build to your servers.

Chef might have more real-time push capabilities; I'm not very familiar with it.

Steps 1 through 3 are commonly automated in a build process. Normally, the output of this process will go through a test cycle. I package the output so that it can be deployed to an integration test environment. Only if the integration tests pass should steps 4 and 5 occur.

Your step 5 implies a deployment outage. For something like apache, this can be handled by shutdown and restart during log rotation. A crontab script can handle this. If you can handle rolling changes over a period of an hour or so just include the restart in the deployment step 4. Puppet or cfengine are appropriate tools for step 4. This can be triggered by updating the repository when the integration tests pass.