Some suggestions from other who have done it
To really see what every state in the United States has to offer would take a lifetime of road trips. But there are a number of folks who have managed to do it much faster. Gary and Peter Flanagan managed to visit all 50 states in just over eight days. More Speed Run information is available <a href = "http://www.roadtripamerica.com/links/Speed-Runs.htm">here<a/>.
Another route you might wish to consider was the one undertaken by the Quest-4 folks on the <a href = "http://www.roadtripamerica.com/links/travelogs.htm">Travelog page</a>.
Sounds like a grand adventure you are planning!
Mark
We spent just about that amount and visited all 50 in 2 months
Our 2001 trip cost us 10k for a family of 4. Lasted a total of 63 days ( covered the US in 43 days then casually returned home). We flew to both Alaska and Hawaii. Stayed mostly in economy hotels, occasionally with friends. Saw 4 national parks, 11 concerts, small towns and big cities.
With your budget and 2 people you should be able to comfortably see all 50 in 3 months. Settle down for a few months in a location you enjoy, make a little money, move on to another until your year runs out.
The 2003 trip in 8 days with my son cost just about 4k. Total trip was 14 days, the majority of cost was gas , airfare, some lodging and food. I'd be glad to help you with routing when the time gets closer to your journey.
Gary