As correctly identified in this answer, the show was indeed Korgoth of Barbaria (NSFW). The 22 minute pilot episode aired on Cartoon Network's Adult Swim on June 3, 2006 at 11:30 PM CST, which was definitely when I saw it. The short glimpse I caught of this show (even without sound) stuck in my mind for over 10 years, probably because it mirrored the surreal surroundings of the destroyed town I was living in at the time. I'm adding this answer to fill in some of the blanks from my question (and my memory).
The pilot was written by Aaron Springer (SpongeBob, Gravity Falls) who also co-directed the episode with Genndy Tartakovsky (creator of Samurai Jack). The voice actors included John DiMaggio (Samurai Jack, Futurama, Gravity Falls) and Tom Kenny (SpongeBob, Adventure Time) and featured an absolutely epic thrash metal soundtrack, composed by Lee Holdridge (Beastmaster). The episode was produced by Cartoon Network Studios and Williams Street and was rated 'TV-MA'.
A description of the show from Adult Swim:
In a dark future wasteland, the great cities have risen and fallen,
primordial beasts have reclaimed the wilderness and thieves and
savages populate sparse, dirty towns. From the frozen north emerges a
warrior known as Korgoth, and his merciless savagery may be his only
key to survival.
The above quote is basically a paraphrased version of the voice-over in the title sequence:
The Great Cities have risen and fallen. Civilization's grip on mankind
has grown weak and arthritic. Dark forces seek to renew forgotten
covenants, and primordial beasts reclaim the wilderness. Out of the
frozen north, a man emerges - a man of a barbaric age, whose merciless
savagery may be the only key to his survival. They call him...Korgoth!
The official Korgoth of Barbaria poster (also a frame from the title sequence):
From the IMDB entry for Korgoth of Barbaria (2006):
Unsold TV pilot and a dark, violent and gory sword and sorcery spoof
set in a post-apocalyptic new dark age about a Conan-like barbarian
warrior hired to steal a golden goblin from a dangerous wizard who
lives in a tower in the sky.
The painted backgrounds in the pilot episode were created by Justin K. Thompson, and several of his early concept sketches for the show are available here (original source here, and compare to one of his earlier works from 2004):
From the Korgoth of Barbaria Wikipedia entry:
...as of December 29, 2007, the only mention of the show on the Adult
Swim website is an intro graphic with the words "you couldn't handle
more than one anyway".
The pilot episode re-aired on Adult Swim on October 31, 2008 and November 3, 2013.
On October 31, 2010, Adult Swim aired a 15 second bumper listing shows that were not picked up:
A comment on the pilot episode on YouTube (by ChiotVulgaire, June 2018) provides some excellent insight into the context of Korgoth's cancellation:
...this show's production costs were simply too big. It's
hand-animated with the vast majority of its assets originally made for
the show, and it doesn't use any time-and-money saving techniques like
tweening or digital coloring. Even the backgrounds are classic
handmade matte painting. Not to mention they kinda shot themselves in
the foot with some big-name voice actors (I hear John Dimaggio, Tom
Kenny, and Diedrich Bader). To make matters worse, CN is still trying
to move to smaller production value stuff including more live-action
content and shorter episode formats. Essentially, Korgoth is
everything they were trying to move away from, which is a shame
because as awesome as everything is, the show itself is more than the
sum of its parts. There's a reason they still show it now and then on
Maybe if Korgoth got picked up by an animation studio that is good at
doing this kind of work for cheap it could live again, but there's
simply no way CN in it's current state will even attempt a second
episode of this show, let alone an actual season.