The change they made in Rails 3 with these data- attributes wasn’t about graceful degradation, it was about unobtrusive JavaScript.
In Rails 2, specifying :method => :delete on a link would generate a whole bunch of inline JavaScript that would create a form with a hidden input and then submit the form. That was the same as it is now: turn off JavaScript and it defaults to a GET request. As such, supporting the case of no JavaScript is the same as it was before.
One option is to use a form/button instead of a link so you can include the method as a hidden field, much like the Rails 2 JavaScript does. Another option is to have the GET version take you to an intermediate page which in turn has the form/button.
The benefit of the new approach is that it’s unobtrusive. The JavaScript for changing the HTTP verb exists in an external file and uses the data- attributes to determine which elements it should be attached to.