"Having said that" is common. So is "that said." The second phrase is just "that said," two words. These phrases mean "however," but are often used in used in a specific situation.
The situation is that of an argument or debate. The speaker is about to say something that mostly contradicts somebody's point of view. However, that point of view is partly right--in some small, technical, unimportant way. So the speaker begin by admitting the small point. He then uses the phrase "having said that," meaning "we can now leave that behind and get on to my main point."
Person A: "Aristotle was right! The heavy stone hit the ground first."
Person B: "Granted, it did hit the ground first. I can't argue with that. Having said that, Aristotle was still totally wrong. Aristotle didn't just say the heavy stone would fall faster. He said that the speed would be proportional to the stone's weight. According to Aristotle, the light stone should have fallen at 1% of the speed of the heavy stone, and in reality it fell at 99% of the speed of the heavy stone."