DantesTenth
So, it seems any attempt to dehumidify the garage would be futile?
No doubt, putting a car in the garage would be a bad idea correct?
When you say tear it down and start over, it seems the best thing to do would be doing the first part of that suggestion only.
Well, where I live is in a 12/24 - 24/24 fogbank, so maybe you’re not in that bad of shape (I’ve seen Boston only once, and that was many, many years before becoming familiar with salt air).
But, if your climate is anything like the local - yes, tear it down or heat it. I am not going to try to heat my basement, and my climate is MUCH warmer than yours - either coat the tools or get something moisture-resistant and heated in which to store them - a detached, unheated space doesn’t have a chance around here (SF area) - and in my case truly raw steel rusts even next to the car (which was built pretty much corrosion-proof in 1986). Having a roof over a car is always a good idea - it beats having water running all over it, looking for an opening - just make sure air can circulate around it - perhaps a carport would be better than a moisture-enclosing structure? What do your neighbors do? Cars have better corrosion protection (plating on small parts, well-applied paint on the other parts) than most tools (I blued a couple of chisels years ago - aside from their cutting edges, they are fine. Then again, I have a couple of automatic center punches - blued steel - which have developed rust around the knurled part. Shrug.
I’m no expert on building science, but here’s my take:
I suspect that your problem is the outside air. The humid air enters and condenses on the floor, walls, tools, etc. The air outside has just as much water in it, but it gets warmed during the day so the relative humidity is lower on average across every twenty four hours.
There may be some water introduced through the floor and walls, but I doubt that it’s the source of the problem. Also, while built up roof are famous for leaking, I don’t think that a leaky roof is causing the high humidity. If it were, then the water stains on the rafters and roof sheathing would probably be obvious. I’m assuming that the ceiling is unfinished, but if there is drywall on the ceiling, then it would be stained as well.
I suggest adding a powered vent. I wouldn’t cut a hole in the roof though, as a hole in a flat roof is an invitation for water to leak in. Just break out a hole at the top of a wall and vent out through a duct or grate. I’d put it on the northern wall or the wall farthest from the door so that there is a cross flow of drier air across the room.
You could also try adding some level of climate control. Natural gas is used around here, and a properly vented gas heater can dramatically lower humidity. I don’t know if an oil burning heater would do the same thing, but I think it would if for no other reason than that it would raise the temperature, allowing the air to hold more water. An air conditioner would extract water from the air in the summer. Alternately, you could just put in a dehumidifier and see how it works. A dehumidifier would be cheaper, but wouldn’t you rather have a warm shop to work in? 
Seriously, I’d try the vent first and save the more expensive options for if the vent doesn’t help.
As danceswithcats said, anything you use to seal the floor and walls inside the garage could blister and flake if the water is coming from the walls and floor. It would be worth testing before you paint, but if the concrete is dry enough to paint then it isn’t your moisture source and I doubt that painting would help.
The reason I asked where you live is because I live in the South, and the rules are completely reversed here. Ventilation can cause higher humidity in the South, while it can reduce humidity in the North. Of course, living near the ocean adds another set of special circumstances.
Sorry, gotta disagree with vent=solution around salt air - it might improve the problem, but not noticably - the wet air enters during the warm hours, then the overnight chill causes the moisture to condense is valid, but at .5 mi. from the ocean, even the night air is going to be moist as long as it is above freezing.
What I really object to is the suggestion of knock a hole in cinderblock (for the kids: these are old (I suspect the cinders were from steam locomotives, don’t know) dirt-cheap building blocks which crumble even faster than the concrete blocks) - that stuff crumbles easily, and without a header to carry the load, I suspect the wall would fail - especially if you opened a big enough hole in which to mount any significant exhaust - a simple vent will do little to displace the air - remember, cold air is less dense than warm (I think), so all a hole would do is invite additional air to enter during the night - not all that helpful.
Then again, if destruction is the only other option, go ahead and poke holes - but do not put anything that can’t fall flat when the structure fails.
For heat, are you using oil? If so, I can’t help you - I’ve dealt with natural gas and propane heaters, never oil. Localy, I understand that the utility company is loathe to add another line, so you might have to run a pipe from the house to the garage. I’d look at baseboard electric heaters - they can do a decent job (so I’ve heard) for small $ of electricity, and running a power line is a LOT easier than running a pipe, especially in areas subject to freezing.
And: why haven’t any N.E. costal residents piped in? This has to be a common problem in your area - again, what do your neighbors do, and have you talked to a contractor about this?
Cinder blocks are so named because they use fly ash as an aggregate. I think that fly ash mostly comes from coal burning power plants. They’re weaker than the concrete blocks they have largely replaced in the market but they still have some strength. It might be safer to place the vent one or two courses down from the very top, but I don’t think that the structure will fail because a block was removed and a vent was mudded into the wall in its place. Besides, I’d assume that anyone doing the work would use a header to hold up any elements, such as a rafter, which bear down over the open gap or better yet locate the vent so that it wasn’t directly under such an element. Also, the top plate running along the top of the wall will help somewhat to tie the wall together.
For what it’s worth, I live in a block house, and the walls have cracked at several weak points, but those are where window openings wrap around two corners, taking the place of the upper half of the wall (it’s really a bad design.) The hole I poked for a dryer vent is doing fine.
Of course, the wall could be taken entirely out of the equation by venting through holes cut into the blocking in a rafter bay or two and making a plenum to direct the fan’s exhaust through the holes. I assume that anyone doing the work will size the holes according to local codes.
I agree with you that venting might not be the solution if the problem is due to salt air from the ocean, but I’m not entirely sure that that’s the case (as of noon today, Boston is at 28 percent relative humidity and well above freezing.) wolf_meister, do cars and metal objects kept outside tend to rust out more quickly than they do farther inland? That might be one way to determine if the salt air is that big of a problem.
I’ll second the idea of calling a contractor. Also, your jurisdiction’s development and review department should be familiar with the problem you’re having. The amount of customer service these departments give can vary greatly, but I’ve found that my city’s building inspectors and engineers are usually happy to offer their opinions and advice.
p.s., Cold air is more dense, but I don’t see how that will affect a fan’s operation.