It doesn't matter if it is extinct or constructed, but I would like some literature available to learn it. The more irregular the better.

I'm looking for a language that inflects verbs to carry tense, aspect, subject, object, and whatever you can cram in there and one that inflects nouns for a bunch of cases, singularity, duality, plurality, definitiveness, and whatever else.

I've heard the Baltic-Slavic branch of Indo-European languages are the most inflected but I'm looking for a specific language.

Not by a long shot. Past tense verbs don't even inflect for person in most of them. What you want is one of the polysynthetic languages. Unfortunately, I doubt anyone here knows them well enough to be able to judge which really contains the most mandatory distinctions.

If you want a really irregular language (it's not polysynthetic or even close), look at Old Irish. It's very irregular.

Old Irish is ridiculous, but I still don't think it can hold a smoldering taper to Navajo. Now there's a verbal system to make anything Indo-European look reasonable!

Some of the languages of the Caucasus are mind-boggling. Tsez has over 120 cases (!).

What's the verbal system like? Anything akin to split-ergativity and mind-bendng screeves of Kartvelian?

Take a look and see if this makes more sense to you than it does to me:http://en.wikipedia.org/wiki/Tsez_language#Verbs

Complex enough, but not as bad as Georgian. Now if only some of those periphrastic tenses grammaticalised the auxiliary to the point of synthesis and then we'd be within sight of Crazytown!

Navajo is definitely a contender. Believe it or not, there ARE rules, just loads of them
But Navajo doesn't hold a candle to Lushootseed or Coeur d’Alene. While grammaticaly it'll make a grown man cry, it's consonant clusters are nothing to sneeze at. While this isn't a typical word, the clusters are typical: xłp̓x̣ʷłtłpłłskʷc̓ . I think it has 17 consonants in a row. "he had had a bunchberry plant"
Tlingit is also nightmarish. I did my dissertation on Tlingit.
I'll give a quick example:
yas'eil - rip
tléil x'éitx yaa ees'él'jeek - Don't tear it open

(vowels will change in the middle of a word!)

s'ísaa woóshdax xwaas'éil - I tore it apart
x'úx' kaxas'él't - I am making a pile of paper
gèiwoo kawdis'éil' - The net is ripped
daak yaawas'él' - earring (it is pierced/torn through)

Maybe some of you can see the root yas'éil throughout. It's easy to say it's obvious when you're reading it, but in "real life", it's the farthest from easy. The underlines letters are separate letters. x sounds like you're coughing up a piece of popcorn kernel stuck on your tonsil, but x' is extra special. It's a mix of that sound plus chunky snot mixed in. (That's how a member of the tribe explained it to me!)
While Cherokee is considered agglutinative, compared to Northwest Pacific languages, it's like Indonesian!

Hmm..the wikipedia says 64...