Not sure about best or least expensive. Different songs in each room means independent amplifiers for each zone, something you can't really accomplish with your current equipment unless you limit it to five zones (or however many channels your hk avr has) and mono sound, and then your avr can't be used for anything else.
But say we add a suitable multichannel amp or amps to the list. One possibility I suppose would be running something like xbmc (if your tablets are up to it) or another android mediacenter type app on each tablet, all pulling songs stored as a collection on the Linux server. Probably dozens of potential apps, including simple ones like vlc, that will vary in balance between hardware requirements, flexibility, simplicity, beauty etc. Each tablet sends line level analog audio back to multichannel amp(s), powering the various zones. Volume could be handled by tablet control (don't know if this is done digital or analog in android devices, probably digital) or the common transformer wall switch/knob in each zone that are widely used for this purpose, or some combination of the two.
Using physically separate amps for each zone might cost more for the amps but would cut way down on the wiring runs required and significantly reduce the potential for nasty noise and hum problems with long low voltage line level runs.
Cool thing about xbmc and possibly other solutions is the possibility of having one tablet control another as a target, letting you say start a song in the kitchen from the bedroom tablet. At least xbmc devs have been working on that, not sure if its exposed in the latest release or not.
Other apps might be better suited for music only purpose, xbmc is more TV/movie centric though it does music and more too. Perhaps someone can recommend something a little more trim on the app side.
There are probably more "proper" or elegant ways to do this type of thing, but stuff like crestron comes to mind and then inexpensive is out the window.