The teaser trailer I'm thinking of is very short and only shows visuals of the characters. But they do not go about speaking, only the woman's voice is singing. I have heard this song in other fantasy trailers, but I can't remember any of the lyrics!
Do you mean this trailer?
If you mean this trailer:
Or if you mean this trailer:
If you mean another trailer then please clarify which one.
The song is Gone by Ioanna Gika used in the Snow White and the Huntsman new movie.
It was also used as a season 3 premier of game of thrones in an HBO clip (still never found it)