The reason the tools don't support this is that it is a rather odd request. I've been there.
The jQuery solutions above will get them what they asked for-- but maybe not what they (or you, as a team) need. I'd definitely go back to the testers (not to fire them!), and try to understand the requirement a little more. Is it really every element? Look at a couple pages together and see what is missing-- maybe they are just frustrated and need a few more IDs than they have.
It's also hard to believe that a testing tool would only be able to address DOM elements by ID; see if there are other options that will work equally well and what you can volunteer to add to support them. (It will certainly be easier than adding IDs everywhere.)
Finally, if IDs are the only way, consider assigning the IDs based on something that will be more permanent than the element count-- some sort of hash of the innerHTML, an element's parent + index, or something like that.
Another thing to consider-- if you need to generate IDs-- is doing it server side. Depending on what language you are in, it may be easier to do there, and won't kill the browser performance.
Good luck!