When I write to someone for the first time, can I say "How do you do?" at the very beginning of the letter?
In informal letter to a friend I suppose you could use anything you like , but 'how are you doing' would sound better.
Is it the formal or informal letter you enquiring about?
Please note: I am not ateacher.
On the "How do you do?" formula I would say "How do you do sir?, if you are trying to be formal. In any formal letter, the "Dear Sir" is always recomendable.
Bottom line, in a letter you can express yourself in any way you want as long as what you are trying to say is understood by the receiver.