I know that, if you join two independent clauses with a coordinating conjunction (like "and"), you need a comma before the coordinating conjunction.
For example: I walked to the store, and I bought some cheese.
You do not need a comma when using conjunctions to join clauses. Maybe, you could say, you definitely do for dependent clauses, but you certainly can get by without them - in formal writing - when joining ind. clauses. Even your example would be fine:
I walked to the store and I bought some cheese.
(Native speakers might drop the repeated subject and just have "I walked to the store and bought some cheese")
Commas are introduced as a matter of necessity with lists, though, so you may be thinking about the actions as a serial sequence of events. But that's unnecessary in your example.
Commas are punctuation, not grammar. Punctuation marks how the reader should approach or interpret text so that they have the same understanding when they read it that the author had when he wrote it. It is also used, along with constructions like meter used to help speakers when they are reading texts aloud.
Generally punctuation and grammar align very nicely and everyone's happy. But as you explore language as you have with your examples, I would say the best operating assumption for commas is that 1) they mark a pause (like a breath), and 2) they should not be overused or you break the cadence of the sentence.
Returning to your examples:
My question is if this holds up when you throw in a non-restrictive clause after the coordinating conjunction.
For example: I walked to the store, and, despite having plenty of cheese at home, I bought some cheese.
or
I walked to the store and, despite having plenty of cheese at home, I bought some cheese.
I would go with the second form. It works like the dependent clause mention earlier; you are setting aside the dep. clause "despite having plenty of cheese at home" from the complex clause of the main sentence.
Good question. I suffered the angst of comma placement for years. It never really goes away =)
Edit: Exception cited by request, NYT article from today:
Before she was found, the authorities said Ms. Pais had traveled to Denver and was considered armed and “extremely dangerous,” leading to the decision to keep about half a million students home in two dozen school districts.
Or, Ms. Pais had traveled to the store and Ms. Pais was considered to have bought cheese