Gmail does work without javascript, it has long been the example I give of competent web authoring. As for when it makes sense, I suggest this guideline: if what you're building is to be a worthwhile contribution to the World-Wide Web, it should have a mode with server-rendered semantic markup behind URLs which are stable forever. Client-side rendering is an enhancement to build after that works well. Your content is more important than the custom behavior you're adding to the the browser the user already chose.
This is exactly the approach I'm doing. I'm writing the app entirely server based, just a couple of ajax do avoid loading unnecessary data at some time.
The time I finish the app, I will tweak and optimize loading either by AJAX or implement something like backbone views.
