Ive never owned a karaoke rig...just rented one a few times when requested to perform a split disco/karaoke.
However, Video technology, I do tend to "keep an eye on".
LCD projectors are now VERY cheap compared to their original prices...my mate bought one 2 years ago for £600 (Made by Sharp), it came with a bulb, which is handy, considering the bulbs cost £250 to replace...they last about 1200 hours. (600 movies...or 41pence of bulb life, per movie)... Therefore, the projector was only £350 in effect.
Size wise, the projector is about the size of a Yellow Pages telephone Directory.
If however, you dont mind something a bit bigger (about the size of a small suitcase) you could consider CRT (cathoid ray tube) projectors. These often have three lenses on the front of them Red, Green, Blue... The lens (or colour guns will go, after about 10,000~20,000 hours, and only cost £100 each to replace. If one "goes" its not the end of the night, just things might change colour.
If I was looking at getting into Karaoke now, on a budget, I'd look at the old "chunky" computer monitors...you can pick them up (mind your back - they're heavy) for about £70 each (secondhand) for a 19inch display - just make sure that they've got RGB inputs, and your DVD or CDG player will output in RGB (if not there are adaptors which will convert it).
Alternatively, I'd look at the 14inch/15inch LCD screens...more pricey, but much easier to transport and fit into small venues.
Ultra-cheap karaoke???? Text the next singers mobile with the lyrics to the next song...