PyObjC on Xcode 4
The Python-Cocoa class templates you're looking for are part of PyObjC, but Apple stopped including them in the install around the end of Leopard (I think), because they got out of sync with Xcode. You can download the latest versions yourself from the PyObjC repository. According to this recent guide I found, they should go in ~/Library/Developer/Xcode/Templates/.
Beware, however: according to Ronald Oussoren, PyObjC's developer, the Interface Builder part of Xcode 4 is not at all compatible with PyObjC. He made a posting to the pythonmac mailing list and another to the pyobjc-dev list suggesting that bugs be filed with Apple, requesting continued Xcode support for the bridge. There's nothing that can be done on either his or your end; Apple has to do this.
You'll have to keep Xcode 3 around to do PyObjC GUI stuff.
I've successfully built a MacRuby GUI app in XCode 4.2 on Lion today following a MacRuby tutorial on Apple's site. MacRuby also includes a template in XCode 4.2. I'm a Python programmer and really hoped to use it, but at this point I've given up on PyObjC. I use Tk in Python for quick little apps and maybe switch to MacRuby, but will likely just switch to Objective-c. Ruby is a pretty nice language though. Maybe MacRuby will interest you.