The Orion spaceship design proposed using nuclear weapons to provide thrust. According to the linked site
Which seems shockingly low to me, even in 1964 dollars. (Apollo was something like $20 billion in cost.)
Given that with the various disarmament treaties the US and Russia have signed over the years, getting the nukes needed to power the ship should be relatively inexpensive. Still, I can’t imagine that the total cost would be all that cheap.
Well, you wouldn’t need to use any exotic light weight-saving materials. Just a whole lot of steel. And steel is cheap. Of course, filling out the EPA reports would probably suck up half your budget.
Nah, assemble it in orbit and launch the various components using Russian heavy lift vehicles from a platform set up in international waters.
You would still have to deal with protest by Greenpeace people in boats, but your right; going into international waters to launch would save a lot on the paperwork. Of course, I would rather use the nukes to get the thing into orbit as well, that way you can send it up in one piece and not have to deal with expensive and unreialbe chemical rockets. Also, using a nuke to launch from the surface would have the bonus effect of clearing out any nearby protestors on their boats. 
Well, that certainly offers a way to help defray the costs (whatever they might be), by selling the rights of the liftoff to pay-per-view. I’m sure the members of the Sahara Club would be all for it.