Any landlocked nations with a Naval service?

And Chad.

There is a Navy base in the middle of Nevada too.

Lots of state governors will confer the title of Colonel on people they like. The governor of Nebraska will confer the title of Admiral. (If you are not laughing yet, I suggest you take a look at a map of Nebraska.

You can even nominate your friends for the dignity:
http://governor.nebraska.gov/contact/

New Mexico has both Navy and Coast Guard contingents. The Coast Guard station operates a radar dish monitoring the border with Mexico. The Navy tests weapons at White Sands Missile Range. The building where they work is referred to as a “Land-Locked Ship”.