DCA is a relatively civilized airport; even without elite frequent flyer status, 4:30 should leave plenty of time, especially if you check in online, use a mobile boarding pass, and do not check bags.
It sounds like you would be staying in Crystal City, for which some practical options include the following:
- If your hotel has an airport shuttle, inquire about early morning service. Some may run on a limited off-hours schedule, or they may be willing to do ad hoc trips. Early flights are not unusual for business travelers.
- For the same reason, some of the larger hotels always seem to have a spare taxi or two waiting out front, 24-7. If it is not there you can call and request one for immediate pickup, or use a service like TaxiMagic. I would allot 15-20 minutes just in case one is not immediately available, but I have gotten one a little before 5am on a weekday within 3 minutes before from the Clarendon area.
- You can reserve a taxi the night before, either by having the hotel arrange for it, or by calling yourself (I like Red Top and Blue Top in Arlington). You could also arrange for a car service or shared airport van, but given the short distances to DCA, I would consider this a waste of money.
In fact, you could walk to the airport from most of Crystal City via the Mt. Vernon Trail, accessible on Crystal St. between 15th and 18th, or via Airport Viaduct— although I would not attempt this after dark as they are not well lit. (For completeness, I will also mention the 9A/9E Metrobus stop at 26th and Rte. 1, near the Airport Viaduct, which does not run early enough for you anyway).