I would create a temporary array each time that contains all the elements from classes except for the previously used class. Then select a random one from that.
JS Fiddle: http://jsfiddle.net/9AbRQ/
var classes = ['addedclass1', 'addedclass2', 'addedclass3', 'addedclass4'];
var prevClass = "";
$('.sometext').each(function() {
var classes2 = [];
for (var i = 0; i < classes.length; i++) {
if (classes[i] !== prevClass) {
classes2.push(classes[i]);
}
}
$(this).addClass(prevClass = classes2[Math.floor(Math.random()*classes2.length)]);
});