I have seen some really interesting designs made from plastic cutting boards -- yes, cutting boards. They're tough, easy to cut/drill/shape and it's also pretty inexpensive. There is also polycaprolactone (goes by various names, but I got mine from a vendor selling it as ShapeLock) -- it's cheap, tough and drillable/fileable. It melts in boiling water and becomes tough when it cools, and has a similar feel to nylon. I'd be sure to keep anything that can get hot away from it though, or your 'bot will melt. :-)
(edit: I forgot to mention that you can make sheets of it pretty easily too: http://letsmakerobots.com/node/4070)
If you want metal, you'll probably want some angle iron of various gauges and sizes, at least for prototyping. I don't know if Meccano is still around, but I made some neat stuff out of that (and Lego too, of course). Aluminum flashing, a pop rivet gun, hacksaw and files. Try to score a small metal brake too for making nice straight folds, and maybe a sheet metal course at the community college to learn how to weld and grind correctly and safely. Try to make friends with the local panel shops, as they usually have enough scrap to keep a hobbyiest in excellent stock, as well as access to some of the bigger tools that you may want to use on occasion.
An assortment of bosses, nuts, bolts, washers, screws and taps is probably going to be high on the list as well, along with your normal assortment of tools for working with these things. A dremel is very handy, as are various pliers, tweezers and such.
Once you build a few prototypes you will know what you're after and can get plastic sheeting or metal stock laser-cut at various places online or if you're fortunate, locally. That really is the ultimate. Maybe take some time to learn how to build up pieces in Blender or a cheap/free 3D CAD package so you can just send the design files off and get back exactly what you're after.
I haven't got any advice on waterproofing. I imagine starting with an already waterproof container of some kind and creating sealed ports would be the quickest method. I'd take a look at electric boat hobbyiest websites and see how they manage.