Let me go through with your points one by one 
this is not a cooling tower to be exact. I do not have a desired initial and final temperature requirements. What I do have is the mass flow and temperature of the water stream in, exhaust gas stream in. I am required to find out the mass of water evaporated. So from my understanding, there will be 3 streams out:
Unless I grossly misunderstood your design intent, my understanding is you have a hot exhaust gas in contact with water (as a mist) and in that regard, you're basically quenching the hot gas.
We cannot ascertain what happens to the process at face value. I can think of two cases however:
1. All the water going in the chamber (we'll call it as such for convenience) is getting evaporated by the hot gas. In this case, you only have two streams coming in (walter and hot gas) and one stream going out (cooled gas)
2. Water flow is too much for the exhaust gas to handle (maybe by poor interphase contact or it's just the water flowrate is too much) and in this case, you'd have an additional stream going out (the excess water)
I feel that an enthalpy balance will be the easiest to determine the mass of water evaporated. I guess i can assume the temperature of the exhaust gas out and the water vapour out to be the same. To keep things simple, lets assume no change in composition for the water and exhaust streams, meaning only counter current contact and exaporation taking place.
This is the problem.
You cannot just assume that they'll be in equilibrium. How long they're in contact as well as how good the contact is will determine the amount of mass and heat transfer between the two streams. And that cannot be determined by heat/mass balance alone.
What you can do however is this:
1. Since you have a fixed amount of water going in, calculate the heat required to ( a ) raise its temperature to boiling point and ( b ) boil of water completely to steam
2. With that amount of heat, calculate the change in temperature of the hot gas from its initial temperature.
If the exhaust gas temperature is lower than the water boiling point, then you can straight out conclude that you won't be able to boil off all the water coming into contact.
If the temperature is higher however, then it's possible that all the water will be converted (and be entrained to the exhaust gas) to steam. Take note that I said "possible" because the possibility of this happening lies on how good the interphase condition is.
It's similar with heat exchangers. Although thermodynamics allow the transfer of a certain amount of heat from the hot to the cold fluid, the actual amount of heat transferred will be controlled (among other factors) by the heat transfer surface area.
Hope I was able to explain myself more clearly 