Here's what I've done in between the Christmas and New Years time period:
Phoenix to Tucson and back
Southwestern Arizona loop (Benson, Tombston, Bisbee, Sierra Vista, Benson)
Flagstaff to Phoenix (had a car shuttle to Flagstaff)
California High Desert (Phelan, Mojave, Ridgecrest, Barstow, Phelan)
San Diego AYH Christmas Trip http://sandiegohostels.org/bikeride/index.htm
Here's what I want to do some day:
Flagstaff, AZ to Victorville, CA (drive to Victorville, take Amtrak with folding bike to Flagstaff, ride back along old Route 66 to car in Victorville)
Another possibility - -
You mentioned Amtrak before - plus you want to do it on the cheap.
What about taking Amtrak to Tucson?
Or better, bike to Tucson and take Amtrak back - prevailing winds are westerly.
Maybe from Oceanside to Pauma Valley and S-22 to Borrego Springs.
Then cut up thru Joshua Tree and to Twentynine Palms and Hwy 62 to Parker.
AZ 72 to Vicksburg, US 60 to Salome, Salome Road to Arlington.
Old US 80 to Gila Bend, AZ 85 to Ajo, and AZ 86 to Tucson.
I'm guessing you haven't toured that much and should stay on pavement and in the U.S. There are lots of places in the desert to pitch your tent for free. The weather should be mild, but the days will be fairly short - 10 hours. Still there may be 50+ mile stretches without services.