It's good that you did the test to rule out the cable and the shuffle itself.
FYI - iTunes 11.x works with my shuffle, along with my other "big" iPods and my iPhone, and I can connect all of them at the same time.
I have tried that and at least once it showed up for just a second then was gone again.
That "showed up for just a second" was in iTunes, or on the Desktop of your Mac? If it's on the Mac desktop, that may be normal, because iPods brieftly appear on the Desktop while iTunes does the initial sync for a few seconds, then iTunes unmounts that iPod's disk and the iPod disappears from the Desktop (unless you have disk use enabled for the iPod). But it should remain visible in iTunes.
In iTunes, you said the sidebar (along left side of window) was not hidden. When no device (such as iPod or iPhone) is connected, you should not see the heading DEVICES in the sidebar. When you connect your iPhone, does DEVICES appear in the sidebar, with the iPhone listed below?