mp3split with script wrapper (Score 1)

I would also go for using mp3split (don't know how it handles very long files - should be okay, because of no re-encoding however).

Wrap it with a simple perl or python script to introduce the randomness.

If that is not sufficient, probably audacity with a custom plugin would be usable.

I would not start with writing a complete new problem, without having evaluated all scriptable options.