If I have the north agenda that gives the military icon to night's watch characters that I control, can I use street of steel to lower the cost of playing one night's watch character without a printed military icon? Or he gains the icon only when in play? Do I "control him" when he is in my hand?

I don't think I can lower the cost, but I'm not sure...

Nope, you could only use the Street if it had a printed M icon, the characters only gain the icons once they are in play.