The Call of the Blade

I am sad to say this, but if You find the skull first, it gives You the next-in-chain quest and You can't take this one :( That's not nice of Blizz.. Somehow Valoren didn't give me this q when I was killing naga in the ruins, so I found skull and thus missed this q forever :((

Guide to Vashj'ir Shimmering Expanse Alliance quests:

The Vashj'ir quests start in Stormwind with Call of Duty.
The immediate pre-requisite for these quests is Across the great Divide which starts in Kelp'thar Forest .

Initial chain:
The Looming Threat
Backed Into a Corner
Rundown
Silver Tide Hollow

Several side quests are now enabled:
Slippery Threat, Don't be Shellfish, and A Distracting Scent
Also a side-chain:

• 
  
• The Great Sambino
• 
  
• Crabby patrons
• 
  
• Undersea Inflation
• 
  
• Totem Modification
• 
  
• Back in One Piece
• 
  
• Toshe's Vengeance (optinal linking quest)
• 
  

The main chain continues at Toshe Chaosrender
Vortex (optional)
Vengeful Heart
Fathom-Lord Zin'jatar
A Pearl of Wisdom (optional;starts from Luminescent Pearl from the boss)
Nespirah
Making Contact
Slave Labor and Stick it To Them
Capture the Crab
Breaking Through
We Are Not Alone
Body Blows, Hopelessly Gearless, and Still Valuable
Overseer Idra'kess
Waking the Beast (also unlocks A Cold Welcome)
A Powerful Need to Eat
Clamming Up and Art of Attraction plus Odor Coater
Bellies Await
You can do all these simultaneously:

• 
  
• Swift Approach
• 
  
• Caught Off-Guard
• 
  
• A Better Vantage
• 
  
• An Occupation of Time (optional)
• 
  

While killing naga, hope Ancient Elven Etching drops to start Piece of the Past
If you do these quests and haven't already continued on the main chain,
The Call of the Blade will set you back on track.

Main chain continues:
Upon the Scene of Battle [You can actually get this quest a bit earlier]
Visions of the Past: The Invasion of Vashj'ir
Turn to Naga and do:

• 
  
• Reoccupation
• 
  
• The Revered Lady
• 
  
• To the Fathom-Lord's Call and Built to Last
• 
  
• Not Soon Forgotten (ends first vision)
• 
  

Looking Forward
Clear Goals, Not Entirely Unprepared, and Properly Inspired
Swift Action
Fallen but Not Forgotten and Gauging Success
Visions of the Past: The Slaughter of Biel'aran Ridge
As a naga again, complete:

• 
  
• By Her Lady's Word
• 
  
• No Trespass Forgiven and Stolen Property plus Chosen Burden
• 
  
• Setting an Example (optional)
• 
  
• The Culmination of Our Efforts (ends second vision)
• 
  

Losing Ground
Desperate Plan
Come Prepared, Unfurling Plan, and Hostile Waters
Honor and Privilege
Welcome News
Visions of the Past: Rise from the Deep
As a naga, work on

• 
  
• Devout Assembly and Her Lady's Hand
• 
  
• At All Costs
• 
  
• Final Judgement (awards Visions of Vashj'ir Past)
• 
  

If you are missing any of the naga optional quests, you may now talk to Wavespeaker Valoren to get the Blade of the Naz'jar Battlemaiden which allows you to repeat any of the visions

This chain [for this zone] wraps up:
A Breath of Fresh Air (enables The War has Many Fronts link to Deepholm)
Full Circle

The Vashj'ir quests conclude in the Abyssal Depths

Where you turn this quest is small skull, I missed it first time but its in the bottom of ocean in the ruins.