When I started out the first step was to figure out a way to write code on my iPhone that could actually be used for an Apple App store submission. I did a fair bit of Googling and after a few of dead ends I came across Pythonista - a fully fledged Python IDE for iPhone (also works on an iPad, but I haven't got one). I already knew the Python language so this looked like a good fit for me. The big question was whether or not there was a way to use code written in Pythonista for an Apple App Store submission. A few Google searches later I discovered that Pythonista has an Xcode App Template which allows you to run Python code written on your phone within a Pythonista Python interpreter running within Xcode (you need a Mac to use this). This basically means that you can write all your code on your phone, transfer the code to your Mac, build it in Xcode and then submit to the App store*. I also found that you could sync Pythonista to DropBox so moving code from my phone to my Mac would be easy.
*Note: if you are think of trying this is that to submit your app to the Apple App store you need to join the Apple Developer Program which is $99 (USD) per year. You don't need to do this right away (I brought my game to a pretty decent prototype before signing up), but you should keep it in mind.
The next step was to figure out how to actually write a game in Pythonista. Thankfully Pythonista comes with some great tutorials and examples. The Game Tutorial turned out to be exactly what I needed - through a series of 7 progressively more detailed scripts it built up a simple (but very nice) space-invaders type game:
The 7 python scripts that make up the Pythonista game tutorial. Each script progressively adds more game elements to build up a full featured space invaders game.
The finished tutorial game (Tutorial Part 7), the man moves with tilt controls.
Building on my pre-existing knowledge of python, by the time I got to the end of the tutorial, I had an outline understanding of how to write an iPhone game on an iPhone. My crazy notion of writing an iPhone game on an iPhone was suddenly looking doable...