ENH: smarter random index selection

Fixes https://github.com/scipy/scipy/issues/3648.

Caveat: The `np.random.choice` function was added in numpy 1.7.0, so we probably need a shim for older versions. I'm not sure how best to accomplish that, so suggestions are welcome.