How large is the room and do you want surround sound or just something louder than the TV?
As for rewiring, that takes all of 30secs per cable if you have a wire stripper, 1min with a knife. The cable that comes with most sets is crap anyway.
Wires running to the front shouldn't be that much of an issue. The rears are more troublesome. You could do what I did and use a single, sleeved cable to run both sets of wires to the back or you could use a wireless transmitter setup just for them.
If you are still dead set on wireless the two original options I gave are pretty much the only viable ones you have in that price range, the 2nd would require you to build the system up over time to stay within the current budget constraint.