The thing is, most of the 'American Idol' type karaoke singers have abandoned MIDI almost completely and migrated to audio MP3's. I don't know if any MP3 player can do markers without some kind of hiccup (I know .wav files can do it), but if you can find something like this, you could simply record your sequences and do it with that.

But I am surprised... a laptop is pretty small. Your workspace must be VERY crowded to make that an impossibility! For all a laptop or desktop could do for making music easier, are you SURE there isn't some older piece of gear you could let go and make room for a computer..?