Between the mountains and the sea?
 

It is said in the poetry that Gil-Galad ruled a kingdom between the mountains and the sea.

Now what mountain is this and what sea is this? I found this phrase also in Silmarillion, in Feanor's rash words to the people concerning that the Valar wishes to shut them up in this narrow land 'between the mountains and the sea'

Obviously, this means Valinor in Feanor's words, so was Gil-Galad's kingdom in Valinor or something?

Gil-Galad's kingdom was in Lindon, between the Blue Mountains and the Sea, all that was left of Beleriand. It's a few day's ride west of The Shire.

At the time of the War of the Ring, many elves still lived there, under the Lordship of Cirdan, Master of the Gray Havens.

Yes, selmo is quite right. The bit about Valinor is about a totally different geographic location.