Create an EXE from a SWF using Flex 3 without requiring AIR

What you need to use is an instance of the Loader class, like so:

var loader:Loader = new Loader();

// you'll need to write a method named onLoaded to capture the COMPLETE event
loader.contentLoaderInfo.addEventListener(Event.COMPLETE, onLoaded);

loader.load(new URLRequest("game.swf"));
addChild(loader);

I haven't been able to figure out how exactly the AIR and Flex SDKs are related.

From an encapsulation perspective, they aren't related in any way. However, Adobe does distribute the AIR SDK with their versions of the Flex SDK.

When using an IDE, such as Flash Builder, a certain directory structure is expected, which includes the AIR SDK in a subdirectory of the Flex SDK.

When using Apache Flex, Apache does not have the rights to distribute the AIR SDK, so it is up to the user to combine the AIR SDK and Flex SDK in a way that makes it easy to use the SDK with Flash Builder. However, the Apache Flex folks are working on an "easy install" tool to prepare the Apache Flex SDK for use with Flash Builder. The tool downloads all the relevant non-Apache binaries and provides you with a finished package.

It is perfectly valid to use the Flex UI Framework without AIR; and to use the AIR SDK without Flex. However, in the Flex SDK, specifically in the mobile component set, I believe there are some dependencies to the AIR SDK. And to use AIR, you will need something to compile it. MXMLC from the Flex SDK is one option.

I'm going to attempt to answer some of your specific questions:

My understanding would have been that AIR enables you to develop Flash (i.e. ActionScript, and apparently also JavaScript/HTML) applications that can be run by the AIR runtime without the need of a browser (such as a pure desktop or smartphone application).

This is true; except I do not believe that AIR has HTML/JS support for smartphones in the same way it does on the desktop. The Mobile AIR Runtime does not include an embedded browser like the desktop version does. However, you can make use of the browser on the device using StageWebView.

The Flex SDK appears to be a collection of classes and additional APIs ...to extend the "standard" Flash library.

This is correct. The Flex Framework provides a lot of UI Component classes, in addition to a framework for building your own UI Classes. To be clear, the Flex SDK includes more than just the Flex Framework, including a step through debugger and the command line compiler.

it appears that the Flex SDK includes some older version of the AIR SDK

This is true; the Flex SDK includes a version of the AIR SDK. Flex and AIR are not on the same update schedule; so Flex would only get updated w/ the latest version of AIR when a new Flex release comes out. There are ways to overlay a new Air SDK onto a Flex SDK if you need it. Here are some instructions. I forget the version of AIR included in Adobe Flex 4.6, but I think it is AIR 3.2. AIR 3.4 is the latest from Adobe.

It is worth noting that Flex has been donated to the Apache Foundation; and they have already released Apache Flex 4.8.

Would I need the Flex utilities to compile?

I'm not entirely clear on the answer to this. Most people use MXMLC from the Flex SDK to compile AIR based applications. Even if you use Flash Builder, MXMLC is used under the hood. If you use Flash Professional, I believe it has it's own AIR Compiler but I do not know if it is based on MXMLC. Flash Builder 4.7 will include a brand new compiler--code named Falcon.

Could I just copy any version of the AIR SDK into a Flex SDK to use both with e.g. FlashDevelop?

In theory yes. I don't know anything about FlashDevelop, however I did understand it had support for Flex. I assume, by extension, it also has support for AIR.