Don't ask me how I did it (ok, you can ask, in fact I'm going to tell you...), but somehow I now have a remote git server and gitolite for repo and user administration installed and running on Ubuntu 11.10 using an Amazon EC2 Micro instance.
I've spent all morning on this, tested it on 3 different instances (I love it how you can just throw away an EC2 instance and start again with a new one in a matter of minutes) and have kept a log of the steps which got me there. Please note that there may be errors or illogical jumps in this summary, but maybe it will be helpful nonetheless - or it may even work outright, who knows.
BEfore we get started, here are some links that helped me (but note I had to pick some steps from some links, and other steps from others...). In particular I did not clone gitolite to my local machine (as this post suggests but ended up using
sudo apt-get install git
First of all, get yourself an instance of Ubuntu (you may swap this for your preferred Linux distro). If you are in love with EC2 then head over to alestic.com and click the selection at the top of the page (I'm using the us-east region), and then pick your preferred image.
The neat thing is that if you already have an Amazon Web Services account you can launch your instance with virtually one click, very neat. I picked the Ubuntu 11.10 Oneiric EBS boot image, 64 bit.
Once booted, SSH into your instance (consult other blogs for details on this if you need help).