Tankless water heater requirements
The tankless water heater can be mounted with either concentric venting (preferred) or dual-pipe venting - one for intake and one for exhaust. Because of this, we would not be able to 'common vent' in with the furnace exhaust or even the chimney itself because the concentric would be pulling air down the chimney or suck in the exhaust of the furnace. We could take the exhaust pipe of the dual pipe option and add it to the chimney or furnace, if sized correctly, but regardless we'd still have to direct vent outside for the intake. So, because of this, it makes the most sense to go with the concentric venting and route it outside.

The best location that we're working with is in that old coal storage room. This provides access to 3/4" water lines and the 1" gas line that we can pull off of for the 3/4" line needed for the water heater. The only workaround now is with venting. The gas meter in my picture is actually farther down the exterior wall than is shown (the gas line does a 90 after coming through the wall) and up to where it's shown in the picture. This allows the easiest access to venting outside through this area, although we're required to keep a 3' distance from the gas meter for it's regulator. This shouldn't be a problem because we actually have to run it up the wall about 3' anyway to clear the snow level. If this isn't workable, the other option is to run the vent to the complete other side of the basement and come out of the wall there. This could come close to the maximum allowable vent span, but it's an option currently.