What options do I have to get to Valencia Airport early in the morning (to catch a flight with departure at 6:30) other than the expensive taxi?
On a weekday, you could take the metro if getting there ~1 h 10 min before the flight is enough for you. (Personally I'd most likely choose this option if, as usual, travelling with just hand luggage.)
According to Metrovalencia's official route planner, the first train (line 3) from city centre (Xàtiva station) leaves at 04:59 and reaches the airport (Aeroport; last stop of the line) at 05:20.
However, on Saturdays the first metro departure is 05:37 (reaching airport 05:58), and on Sundays 06:57 (-> 07:18), so you'd have to look at other options. A taxi wouldn't be that bad, IMHO, as they are relatively cheap in Spain, and as Mark pointed out, the distance isn't huge.
The bus from Túria station departs every 30 minutes and takes about 30-40 minutes. Subway goes directly from the town centre and links the Airport to the main train station, Estación del Norte (beside Xàtiva metro stop), running every 8 minutes and taking about 20 minutes.
A taxi ride from the Calle de La Paz (which is in the heart of the historic city centre) to the airport and covering a distance of approximately 11km costs around €10 potentially with an 'airport supplement' of around €4. The tariffs are on display in the taxi in Valencian, Spanish and English but are difficult to see. The same journey back from Calle de La Paz to the airport half the price! These fees are accurate as of August 2008.
However, I'm uncertain what time the buses and subways start, however your hotel/hostel could help you out there.