BIAB is a great idea, but if you don't want to use a computer, you could do worse than pick up a second hand Yamaha QY. These little boxes allow you to program and play backing tracks for your songs all in one portable video cassette sized box.
Check out the review:
http://www.soundonsound.com/sos/Oct01/articles/yamahaqy100.asp The sounds and styles are not as good as a PSR3000 or what you might get from a PC but they do have the advantage of being a literal band in a box and they're cheaper than the other options.
Ebay always has a selection of different models to match your budget. The latest model and therefore, most expensive, is the QY100 which you can pick up secondhand for around 300 Euros.