Stop popping off the array and use an iterator instead.
var messages = ["Red Bull", "Smoke", "Babes", "css", "batman"],
i = 0;
(function change() {
var msg = messages[i > messages.length - 1 ? (i = 0) : i++];
$("#msg").html(msg).fadeIn(750).delay(2000).fadeOut(750, change);
})();