The phrase is having said that. It's a pre-formed phrase in the lexicon, and you should learn it as a single unit.
In the Corpus of Contemporary American English (COCA), I searched for both phrases using the query
. having said|that said|that ,. I found 367 results for having said that at the beginning of a sentence, and 0 results for having that said. Likewise, in the British National Corpus (BNC), I found 111 results for for the former and 0 results for the latter.
These results show that people don't really reverse the word order – or if they do, that they don't do it very often. In this case, said is a past participle in a perfect construction, not a participial adjective derived from a verb form, so it uses the standard word order with the object following the verb. The other word order isn't ungrammatical, but I recommend you stick to the usual way of saying it.