hmmm, I'm not really knowledgeable in QoS. If you like, you could explain to us what bandwidth problems you have?
Yes, sure you can do the "4 port nic, 4 un-manageable switches" plan. Let me add also, that there could be a way to do it with a 1 port nic instead of the 4 port nic, on the linux box, by using logical "sub-interfaces". I'm not sure that Zebra or any routing package would support this, but on a typical cisco router, it's possible. You would define sub-interfaces (each for a one VLAN) all on one physical interface of the router. Then connect that interface to the man. switch. It will act just like the 4-port nic.