Embedding Python in an iPhone app
It doesn't really matter how you build Python -- you don't need to build it in Xcode, for example -- but what does matter is the product of that build.
Namely, you are going to need to build something like libPython.a that can be statically linked into your application. Once you have a .a, that can be added to the Xcode project for your application(s) and, from there, it'll be linked and signed just like the rest of your app.
IIRC (it has been a while since I've built python by hand) the out-of-the-box python will build a libPython.a (and a bunch of other libraries), if you configure it correctly.
Of course, your second issue is going to be cross-compiling python for ARM from your 86 box. Python is an autoconf based project and autoconf is a pain in the butt for cross-compilation.
As you correctly state, making it small will be critical.
Not surprising, either, is that you aren't the first person to want to do this, but not for iOS. Python has been squeezed into devices much less capable than those that run iOS. I found a thread with a bunch of links when googling about; it might be useful.
Also, you might want to join the pyobjc-dev list. While you aren't targeting a PyObjC based application (which, btw, is a good idea -- PyObjC has a long way to go before it'll be iOS friendly), the PyObjC community has been discussing this and Ronald, of anyone, is probably the most knowledgeable person in this particular area. Note that PyObjC will have to solve the embedded Python on iOS problem prior to porting PyObjC. Their prerequisite is your requirement, as it were.
I've put a very rough script up on github that fetches and builds python2.6.5 for iPhone and simulator.
http://github.com/cobbal/python-for-iphone
Work in progress
Somewhat depressing update nearly 2 years later: (copied from README on github)
This project never really got python running on the iPhone to my satisfaction, and I can't recommend using it for any serious project at this stage.
Most notably missing is pyobjc support (which turns out to be much harder to port to iPhone since it relies on more platform-specific code)
Also missing is the ability to statically compile modules, (all are currently built as dylibs which works for development, but to my knowledge wouldn't be allowed in the App Store)
At this point this project is mostly meant to be a starting point for anyone smarter than me who wants to and can tackle the above issues.
I really wish it were practical to write apps entirely in Python, but at this point it seems impossible.
I also started such a project. It comes with its own simplified compile script so there is no need to mess around with autoconf to get your cross compiled static library. It is able to build a completely dependency-free static library of Python with some common modules. It should be easily extensible.