Etiquette for declining a tenure track job offer I have a good idea of what things to say in my correspondence regarding this matter; here I'm mainly asking how to deliver the news: by phone or by letter/email. 

I have received conflicting advice about this. In many jobs (academic or not) the most common advice seems to be to make a phone call, followed up with a confirmatory email or letter. Specifically in an academic setting, I have heard at least two chairs/deans say something along the lines of "Call me with good news. Email me with bad news". Others have said "use the same medium the school used to contact you"-- in most cases I've heard of, the school often uses a mix of written and telephone correspondence. 

In my particular case, declining the offer by phone would require scheduling a phone call through an intermediary, because all previous correspondences have gone through the Dean's secretary (sending contracts, scheduling previous phone calls). Based on the non-instantaneous scheduling of our other chats, I suspect this would delay things by a few days (so, it wouldn't be like I could just call his office number for a quick chat). Regardless, it seems rather awkward to go through this process of scheduling a phone call just to say "No Thanks". 

Any advice on the general question and/or my specific situation is appreciated.
I would say that the most appropriate medium would be to send a written communication, either as an email or as a letter. This carries much more weight than a phone call, as you actually have something resembling a paper trail that you can provide. 

Although there is a certain wisdom in the advice "contact them as they contacted you," this is an exceptional enough situation that deviating from that rule seems more appropriate.

The route that I would use is to write a formal, signed letter, then scan it in and send a copy of the scanned letter as a PDF to the intended recipient. The scan will reach them more quickly, and you'll still have the formal communication sent by regular mail.