UPDATE I wrote a new article based on Ben Hutching's response.

Just a quick post, mainly as a reminder for when I'll try to implement this in WICD:

#!/usr/bin/python

import gudev

client = gudev.Client(['rfkill', 'net'])

for dev in client.query_by_subsystem('net'):
    if dev.get_sysfs_attr_as_int("type") != 1:
        continue

    driver = dev.get_driver()
    if not driver:
        parent = dev.get_parent()
        if parent:
            driver = parent.get_driver()

    print type, dev.get_name(), driver, dev.get_sysfs_path()

This will print all network devices with ethernet-encapsulated packets (that's what sysfs type "1" is). Here's the output on my system:

eth0 e1000e /sys/devices/pci0000:00/0000:00:19.0/net/eth0
wlan0 b43 /sys/devices/pci0000:00/0000:00:1c.1/0000:10:00.0/ssb0:0/net/wlan0

I'm still missing how to reliably detect if a device is a "wired" or a "wireless" one. I suspect that checking the existence of /phy80211 would be enough, but I can't really tell, and seems like I'm not able to find an exhaustive sysfs reference manual.