This happened on my 1st car. Saying they will have to break the wheel is a load of bol***ks as long as the wheel nut is not the complete circular nut with a 'jigsaw piece' in the middle. If its these, maybe U R knackered, but there must B speciallist tools to remove these.
If the nut has bevels etc on its outside edge you can do it yourself. Hammer a smaller socket than the nut onto it and turn it to remove it. This may completely fook both the locking nut and 4 sockets but U will have your wheels off!