Hybrid page-based / single-page web-app (Angularjs, Ember.js) with progressive enhancement?

This questions is a bit of a nuanced one because the answer is "it depends". For example you mentioned Gmail, there isn't any reasons whatsoever that an application like Gmail would need to be indexed for SEO, though depending on what you want or need to support you may want to ensure you can support not having Javascript.

However even the "no-javascript" argument is getting tired and weak these days, at least for the class of "web applications". If I want to use a Windows application I need Windows, if I want to use a javascript powered web application it isn't unreasonable to assume that I'm going to need a browser that isn't crippled to use it.

However back to your question I can only speak to AngularJS because I'm the most familiar with it. For the most part it does allow you to support a progressive enhancement approach, though don't expect to use things like URL routing if this is what you want to support. What you can do is use AngularJS controllers, bindings and directives similar to how you might use jQuery as a way of enhancing the interactions and behaviours of the page.

Just keep in mind this approach will seriously limit what you can do with Angular (or Ember for that matter) and it may start to be debatable what you are getting from this approach that you couldn't easily do with jQuery alone.

The alternative these days is to do what sites like Twitter are doing. That is basically serve fully rendered HTML from the server for any view on the initial load and then use Javascript for subsequent loading and enhanced UI behaviour. This is very effective (though perhaps quite challenging to implement) if you really need to support browsing with and without Javascript and has the added benefit of improve the rendering/load times for the first request. Again "it depends" because it depends a lot on how your site actually works if it is possible to use this. You have to design for it, and it isn't going to be trivial or easy.

Update:

For what it's worth we are taking the Year of Moo approach and rendering the pages that need SEO using PhantomJS and sticking the cached initial state of them somewhere to serve them up. We have a rake task we run on deployments to update this. Again this is just the initial state but it helps get around the issue for now.

Things are always changing though and I'm sure I will have changed my mind on this approach in a year or so.

Have you read Google's Making AJAX Applications Crawlable. You can have JavaScript single page app and crawlable content.

If you stick with angular, there is interesting article: Turns out it is possible to have your AngularJS application indexed