1. Was Syrio just another swordsmanship teacher who so happens to be in King's Landing when Ned Stark was hiring? Or did Ned know Syrio Forel before?
As you said, it looks like Syrio Forel was around King's Landing when Ned Stark was hiring.
Ned frowned. The man Syrio Forel had come with an excellent reputation, and his flamboyant Braavosi style was well suited to Arya’s
slender blade, yet still ... a few days ago, she had been wandering around with a swatch of black silk tied over her eyes. Syrio was teaching her to see with her ears and her nose and her skin, she told him. Before that, he had her doing spins and back flips. “Arya, are you certain you want to persist in this?”
She nodded. “Tomorrow we’re going to catch cats.”
“Cats.” Ned sighed. “Perhaps it was a mistake to hire this Braavosi. If you like, I will ask Jory to take over your lessons. Or I might have a quiet word with Ser Barristan. He was the finest sword in the Seven Kingdoms in his youth.”
2. What is the First Sword of Braavos doing in King's Landing?
Syrio Forel was no longer the First Sword of Braavos. He himself mentions that.
“The steel must be part of your arm,” the bald man told her. “Can you drop part of your arm? No. Nine years Syrio Forel was first sword to the Sealord of Braavos, he knows these things. Listen to him, boy.”
Most probably he was looking for a job.
At this point, there isn't a lot of information on Syrio Forel.
Updating my answer based on GRRM's interview
Well, I’ve never given it much thought. Ned was searching for a fencing master who could teach Arya, and he knew it couldn’t not be a conventional master at arms or a knight, or the castle master at arms, because he didn’t think his young daughter could handle a broadsword (or maybe longsword) the way man with greater strength in their torso could, so he decided the Braavosi style suited her best. Who was available in the city that might fit the bill? Obviously, somebody had to recommend him to Ned. I believe Syrio must have been in the city at the time, because there wasn’t enough time to send for someone all the way from Braavos.