Where can I get Python VTE bindings for the Mac OS X?
Macport has it. You may install MacPort and do a 

sudo port install vte


NB: Installing vte trough MacPort install a new python in /opt/local/ and vte gets installed in /opt/local/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/site-packages/gtk-2.0