To answer your question directly; you would need to get in after the SiteResolver. Since you need to know what site you're on, to deliver your sitemap. It sits near the top in the <httpRequestBegin> pipeline.
<httpRequestBegin>
<processor type="Sitecore.Pipelines.PreprocessRequest.CheckIgnoreFlag, Sitecore.Kernel" />
<processor type="Sitecore.Pipelines.HttpRequest.EnsureServerUrl, Sitecore.Kernel" />
<processor type="Sitecore.Pipelines.HttpRequest.StartMeasurements, Sitecore.Kernel" />
<processor type="Sitecore.Pipelines.HttpRequest.IgnoreList, Sitecore.Kernel" />
<processor type="Sitecore.Pipelines.HttpRequest.SiteResolver, Sitecore.Kernel" />
So you would not be implementing an IHttpHandler as you suggest, you would instead inherit from Sitecore.Pipelines.HttpRequest.HttpRequestProcessor.
If I may; I'd like to add a few architectural considerations to the mix as well.
Be careful not to "render" your sitemap in real time on these requests. It's usually a very "heavy" operation and you open yourself up quite easily to a denial-of-service attack by doing so.
Instead I propose you add sitemap generation as a scheduled task in Sitecore, to regularly (like hourly/daily/as appropriate) generate sitemaps for each site, and the processor in question only concerns itself with streaming back that generated sitemap to the client.
IHttpHandlers usually execute before a Sitecore.Context is established - this is exactly the job of the <httpRequestBegin> pipeline.