Obviously that a much easier, simpler and (I think) even cheaper alternative would be using some PaaS offering (Jenkins as a Service).
However, I ended up using AWS Cloudformation to automate the provisioning of the AWS Resources (IAM User, SecurityGroup, EBS Volumes, EC2 instance) and its cloud-init features to install and configure the necessary packages.
External repository addition, yum based package installations, configuration files adjustments, EBS volumes setup, etc. Most of the installation and configuration logic is in a shell script embedded in the UserData property.
The resulting template is right below, the input parameters are: Instance type, JENKINS_HOME volume size in gigabytes and the EC2 KeyName. The output is the Jenkins server URL!