What's really interesting is that "google" didn't see this coming - they made angular, they should in theory be huge advocates of SPA, but in reality their primary product doesn't support it well at all.
The angularjs.org sites are indexed, just by using a trivial nginx directive to selectively serve partials to crawlers. All of the angularjs.org apps still rank fairly well using this strategy.
This isn't always appropriate of course, those apps aren't really relying on data from a database, they're proper SPAs. But as noted by others, there are ways to fool crawlers if it's something you want to do.
Generally though, the feeling is that crawlers not executing JS is going to end, and the problem will go away on its own.