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 Saturday, 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).
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 pilot was written by Aaron Springer (Samurai Jack, SpongeBob, Gravity Falls) who also co-directed the episode with Genndy Tartakovsky (producer of Samurai Jack and Primal). The voice actors included John DiMaggio (Samurai Jack, Futurama, Gravity Falls, Disenchantment, Rick and Morty) and Tom Kenny (SpongeBob, Adventure Time, Rick and Morty) and featured an absolutely epic thrash metal soundtrack, composed by Lee Holdridge (Beastmaster, Moonlighting, The Mists of Avalon). The episode was produced by Cartoon Network Studios and Williams Street and was rated 'TV-MA'. Korgoth was originally scheduled to run as a full season in September 2006, but was never picked up by the studio.
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 pilot episode originally aired on Adult Swim on June 3, 2006, and was re-aired on: June 4, 2006; October 31, 2008; January 6, 2011; November 3, 2013 and January 28, 2019.
The official Korgoth of Barbaria poster (also a frame from the title sequence):
Reasons for not picking up the show
By the end of 2007, the only mention of the show on the Adult Swim website was the following graphic:
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.
The painted backgrounds in the pilot episode were sketched by Justin K. Thompson and painted by William Wray, and several of Thompson's early concept sketches for the show are available here (original source here, and compare to one of his earlier works from 2004):
Posted by William Wray on May 31, 2006:
The backgrounds were layed out by one of the best young background
artists out there right now Justin Thompson. I did some final
paintings and some rough keys, here is a selection along with a fake
title card. The big bar pan was cut for time so this will be the only
place you will see it.
Wray additionally explains the time-saving process he used to paint the backgrounds, and pointed out that the Korean studios (typically heavily relied on for reducing animation costs) would not (at the time) use this process for time-saving. This explains the "too expensive" quote in the Adult Swim bumper:
90% Cell paint with some small digital enhancement. Mostly contrasts
and soft light. Drove everyone crazy because everyone is convinced the
Korean [studio] can't understand that concept. One of my goals in
life is to drag them into the digital age. Mixing the two saves so
much time and give[s] you so much more. I print the drawing out
directly onto Water color paper and paint them up fast and sloppy for
the vigor of it. Then I fix the slop and enhance on Photoshop. In a
pinch in the end I just took the pencil directly into Photoshop and I
think they look a little graphic, but still good.
And also indicated that the backgrounds could have been used better by the animation studio (likely involving scene framing and panning, or color use/style by the overlaid animation):
...the Korean [studio] did a preety (sic) bad job on the backgrounds, but that just kind of added to the joke of the show
On October 27, 2009, the pilot episode of Korgoth of Barbaria was released on DVD as part of the 7-disc [adult swim] in a Box, with Korgoth and four other pilots included on disc 7.
Since March 7, 2015, the complete episode can be streamed from the Adult Swim web site.
Spiritual Successor: Primal
On October 7, 2019, Genndy Tartakovsky launched a new animated series on Adult Swim, named Primal (IMDB), which is available on iTunes Movies as a compilation of all episodes in a single "movie". In addition to sharing several artists and cast members from Korgoth of Barbaria, the design of the main characters (a caveman and dinosaur) bear more than a passing resemblance to Korgoth and the dinosaur from the opening credits of Korgoth of Barbaria, although the artistic style is less detailed and closer to that of Samurai Jack (perhaps this lowered production costs to address the problem with Korgoth of Barbaria).
Additionally, the tagline of the show borrows several phrases from that of Korgoth of Barbaria:
Primal features a caveman at the dawn of evolution. A dinosaur on the
brink of extinction. Bonded by tragedy, this unlikely friendship
becomes the only hope of survival in a violent, primordial world.
Compare and contrast the above to this opening credits scene from Korgoth of Barbaria:
There are stylistic differences but many of the same elements are present in the new show. That doesn't make Primal a true successor to Korgoth of Barbaria, but it looks like it may be the closest thing we're ever going to see. One thing in particular to note is the better match between the backgrounds and animation in Primal as contrasted to Korgoth (less detail, more stylized, better blending) - this is what William Wray must have been lamenting about the production studio's work on Korgoth.