I want to protect the clients from sslstrip attack. HSTS should be used. But HSTS does not protect the first visit of the client to the server. So I want to include HSTS policy in dns replies and send to clients that are requesting. Is it possible? If possible, how to implement it?
Not with the current standards and norms, to the best of my knowledge.
The most obvious DNS Query is the A record and I don't see a direct way to incorporate HSTS there - unless it is included in the additional info section of the DNS Response.
The other alternative (and most used/abused bit of DNS) is the TXT record.
Since there is no standard, de-facto or otherwise, it does need widespread browser implementation before it can work. I don't know if there is enough motivation to do this, because of the available option of HSTS Pre-load (see here, here and here). It is fairly easy to ask to preload your domain on to the major browsers. It is also easy to break your apps if you miss renewing / getting certs for any of your infra - after you get into the list (yes, it seems to happen more frequently than we think).
We could argue that wiring it into DNS is better plumbing (giving the earliest opportunity) but given the difficulties DNS has had over the years in its attempts at security (DNSSEC in particular), it has its issues.
So for now, HSTS-PreLoad is the practical, available and widely implemented, if not perfect solution; not DNS.