If we have to preserve backward compatibility of Python AST API, we can do this relatively easily (at the expense of some code complexity):
* Add 'version' argument to compile() and ast.parse() with default value of 1 (old AST). Value 2 will correspond to the new AST.
* Do not remove Num/Str/Bytes/Ellipsis Python classes. Make PyAST_obj2mod and PyAST_mod2obj do appropriate conversions when version is 1.
* Possibly emit a PendingDeprecationWarning when version 1 is used with the goal of removing it in 3.5

Alternative implementation is to leave Num/Str/etc classes in C as well, and write visitors (similar to folding one) to convert AST between old and new forms.

Does this sounds reasonable? Should this be posted to python-dev? Should I write a PEP (I'd need some help with this)?

Are there any other big issues preventing this to be merged?