I tried the same clamp fix with the same results. The problem as I see it is that you cannot replace a straight section with that coupling.
I tried some "muffler bandage" wrap prior to clamping it up in an attempt to seal it but that did not work. I have a feeling that furnace cement will not hold up to the vibration at a joint. Same thing with the Permatex stuff.

I think the best way is welding but am reluctant for the same reasons you are.

You could go new cat + muffler for only around $600 in parts!

Maybe try a different muffler shop - like a custom shop that will build an exhaust for you. Although then you may be looking at more than you want to spend. I'm not so impressed with the quality of goods from Midas / Mienike etc.

--
"Differences of opinions should be tolerated, but not if they're too different' - Sharon Craig