but I can't find anywhere that specifically states that you must provide a working non-JS version
But somewhere you got the idea that JS is prohibitive. This most likely comes from the first version of the WCAG (Web Content Accessibility Guides), where they did say something along the lines of, if you use scripts, they must either be only for pretty extras, or you must somewhere else have a non-scripted equivalent.
WCAG version 2 however sorta undid that, because WCAG2 focusses more on "does it work?" without mentioning specific technologies so much (sometimes it does, like Flash...).
In general, if your site MUST be DDA compliant (taking into account what Mat30 said), I would say:
Most screen readers don't handle JS well. If they do, what usually happens is they'll start rereading the whole page whenever something changes (which can get very awkward).
They do pretty well today, but the issue you bring up is still sometimes a problem.
Take a good look at the new ARIA roles and attributes that are getting more and more support in browsers and screen readers.
Start with ARIA landmarks, they are the easiest to get started with in my opinion.
Then check out how ARIA is used in things like widgets: Here's an awesome example of a typical "slider" used in forms by Filiament Group. Paciello Group (first link) has an ARIA tutorial with things like sliders and whatnot.
[Marco Zehe's English blog also has some how-to's that helped me see how to use ARIA in code. The HTML code itself isn't very good, but just focus on how the ARIA stuff is used. (Look for "Easy ARIA Tip #something" [url=http://www.marcozehe.de/category/aria/]here](http://www.marcozehe.de/)).
Live regions will probably be the hardest part to deal with, partially because the authors are still figuring stuff out themselves, but this helps screen reader users deal with things moving and changing on the page dynamically (without full page refreshes).
ARIA is pretty much ONLY for screen readers, but they're also usually the hardest group to accomodate, and ARIA helps.
Lastly I guess if you've got stuff appearing on the page without page refreshes, another group to be aware of would be those using screen magnifyers. These may or may not be used in conjunction with a screen reader. Basically the user sees a part of your page... about the size of a credit card. So if the user is looking at a part of your page where they must click things or select things, if something changes on the other side of the page, these people would not necessarily notice or know. Making sure changes happen close to where the user event occurs will help many people... and when that's not possible, have at the pace where the event occurs (since that's where user attention is at the moment) an alert to the user that another area is now changed ("Your shopping cart has been updated!") somehow.
You're asking about legal compliance. Get someone familiar with your country's laws to look over the site first. If this site was built JS-first and that is the core functionality, then if it does NOT meet your country's laws or guidelines, it very likely will need to be rebuilt since that's almost always easier than fixing. Accessibility is easier built-in than bolted-on. So get someone who can make sure if you do this sort of large investment that you do it right. Do not rely on automated testing tools (they can help, sure, but no more).
And this might sound terrible, and of course goes against my moral principles etc, but since rewriting a site is expensive, you may want to look at the cost of any lawsuits or fines vs the cost of redoing the site before making your decision. Obviously it would rock if the site just freakin worked for everyone, but...