Since I don't see the reason for not adapting the simplest solution (from a user standpoint), I feel I'm looking at this in a very naive way, but anyway... why not just leave the current theme site as it is, modifying this:
The "normal" download would work for 3.6 compatible themes (i.e. the current versions). The current parser puts a "Works with current build", that would be changed for "Doesn't work with current build" and a link for downloading the converted version. If a theme is uploaded with the new syntax, it would work as it works currently (i.e "Works with current build" and no "Works with realease 3.6)
I don't know the statistics, but my guess is, the majority of users use the stable version when available for the target, so IMHO, things should be oriented accordingly. When the new syntax is in the stable version (3.7?), the current themesite scheme could be used again having only the new syntax compatible theme versions.