You may not be totally out of luck. You only need another cable between the fixtures, and if they are both in the same ceiling between two joists and there is no blocking in between, you may be able to pull it by just removing the boxes.
If that is not an option, you may be able to get your lights to work using an X-10 controller or something similiar for one of the switches. To do this, replace the upstream switch with a remotely controlled switch and wire it normally. Attach the message wire to the hot and splice it and the neutral all the way through to the other switch. Replace the other switch with an remote control for the first.
I'm sure that's as clear as mud, but if you look at the X-10 switches available, perhaps it will become clearer. I've seen an arrangement like this for old work ceiling fans.
