I recently used relayrides.com to rent a vehicle while on vacation. It's like an airbnb for people that want to rent their own cars.
I used a debit card, but I imagine if you were to arrange your own auto insurance you could contact some of the renters on the site and offer them bitcoin instead of making the payment through relayrides.
It's not the most reliable idea, but it's the best I've got right now.
That is pretty sweet. I had never heard of this service. I am sure a competitor will likely come out with the option to pay in bitcoins like airbnb's competitor 9flats