You have the decoded data that you send to OpenAL. While decoding/streaming, you can store it somewhere (either RAM or disk) and jump to a 'N byte aligned random offset' and pass the next samples to OpenAL again.
That would eliminate the resource-saving benefit that you get from streaming an OGG (i.e. taking advantage of the small size of OGGs and only hanging onto to a small chunk of the much larger decoded data at any one time).
I actually need something like this as well for a method I'm adding to my sound library, so I'll post the solution if I happen to discover it before you do, princec.