Search locally and you will find.
A friend of mine bought his combo with 13,000 miles for under $4k! Came with an LS2 intake too.
As far as Zs go, you're in the land of the plenty! California and AZ are some of the places with the most rust free Zs. I know you're looking for a 240z, but why not look into a 280z as well? They seem to run cheaper and are a little more stout frame wise then the 240z's. I picked up mine with a rebuilt engine, lots of new parts, big rims, and a parts car for $1800.
And it is +97% rust free. The floor pans look great, as do the rails, spair tire well doesn't even have surface rust, as does the battery tray! Only had rust by the front passenger headlight.
Even though eBay is a good place to look, being in CA, you can usually beat the prices by looking in local car selling magazines/classified/newspapers.
Best of luck!
Mario