Alright, but is it really not possible to do it with the wireless shield ?
Have you removed the ATMega328 chip from the Arduino? That is necessary, as it interferes with the serial communication that takes place between the USB to serial converter chip and the shield with the XBee on it. Without removing the ATMega328 (pay attention to its orientation, so you can put it back correctly), I don't know of a way to use the Arduino/XBee shield to program the XBees.
I'll get an USB explorer
You won't regret it. I have two, so I can program and test two XBees at a time.