I'd say try and get past the snags, because it fits the all of your requirements pretty much perfectly apart from speed.
Python has always been designed with extending and embedding in mind, and it's pretty easy to do so. My first job involved a large management information system in which clients had embedded Python interpreters which ran scripts which in turn used wrappers around a set of CORBA objects representing various elements of a job. The initial time to implement the embedding was minimal and wrapping objects is generally more a matter of patience than skill or time... in fact I think there are automatic wrapper generators available.
Python also supports restricted execution through either the rexec or Bastion modules, and even without those you can create your own namespaces using dictionaries and have code execute in those rather than globally to ensure security. If you look at the code for MOOP, a MOO written in Python, it does a similar thing for user-defined functions using some cunning hacks...
Also, another thing MOOP does is compile Python code on the fly from a string and execute that, using Python's built-in compile() function, so you could pass in code in a C string.
Speed may be an issue because Python isn't particularly fast in itself, however if most of the leg-work is going to be done inside the wrapped C/C++ code then this shouldn't be so much of a problem. Just make sure any processor intensive stuff is done from the C/C++ stuff and the Python is used for controlling it.
And of course, Python is open source, so no problems there...
You're doomed, I'm doomed, we're all doomed for ice cream. - Bob Aboey