If you must use travelers' checks, getting them in the country's currency is a good idea, but if you ask about the buy/sell spread you'll find out that you're still paying for the convenience, even at AAA.

My impression is that the order in which the OP has listed the options is the preferred order of use if exchange rate is the main issue. Another variable for using credit cards is to know what exchange fee is charged by your bank. MBNA and CapitalOne are two large CC issuers that only pass on the 1% Visa/Mastercard fee with no additional charge of their own. Most other banks add 1 to 3% to the exchange. Amex's fee is 2% (but the exchange rate that Amex uses isn't necessarily an "official" interbank rate).