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.