New soldering iron turns black as soon as it reaches 350C
I can't even tin it as it turns black before I reach melting
  temperature.


What kind of solder is that?!

The highest melting point of the eutectic solder I have ever seen was around 300°C. Most of the commonly used solders melt way under 250°C. No wonder your iron tip turns black.

This is not to say there are no solders that need higher temperature, only that it is highly unlikely you'd ever need one.

Another possible reason for tip turning black is using plumbing solder or flux.