Practically speaking, how broken is SSLv3.0 now? Are we hours, days, weeks, months, or years from someone actually getting out there and exploiting this?
This is exploitable now. Padding oracles have been found before, and are even homework assignments of the Coursera cryptography course. The specifics of this bug make it a little bit harder but the paper explains how to work around this. Expect this bug to be exploited in the wild since minutes after (or perhaps already before) the release.
You need 256 requests to get one byte of clear text. A 160bit session key is likely to be 40 bytes, so that's 10,240 requests to get the session key - it might actually be less if you can take shortcuts because you know the result bytes can only be 0-9a-f. You also need to be a man in the middle.
