Solution 1:

Thanks to @A-B who made me aware of the reason behind tc not filtering.

I do use MASQUERADING on all external interfaces and it seems that those rules are applied before tc can filter the packets. This results in the following recommendation:

If you are using a MASQUERADE-rule on the outgoing interface you need to use the fw-filter from traffic-control and mark the packets using iptables.

This might seem obvious to the more experienced users but its not mentioned anywhere and (at least for me) its hard to find out.

Example:

#!/bin/bash
tc=/sbin/tc
ipt=/sbin/iptables

$tc qdisc add dev eth0 root handle 1: htb default 30

# shape general uplink speed
$tc class add dev eth0 parent 1: classid 1:1 htb rate 5.0mbit burst 6k
$tc class add dev eth0 parent 1:1 classid 1:10 htb rate 2.0mbit ceil 4.0mbit burst 2k prio 1
$tc class add dev eth0 parent 1:1 classid 1:20 htb rate 2.5mbit ceil 4.0mbit burst 3k prio 2
$tc class add dev eth0 parent 1:1 classid 1:30 htb rate 0.5mbit ceil 1.0mbit burst 1k prio 3

# stochastic fairness
$tc qdisc add dev eth0 parent 1:10 handle 10: sfq perturb 10
$tc qdisc add dev eth0 parent 1:20 handle 20: sfq perturb 10
$tc qdisc add dev eth0 parent 1:30 handle 30: sfq perturb 10

# filtering on eth0
$tc filter add dev eth0 parent 1: protocol ip handle 10 fw flowid 1:10
$tc filter add dev eth0 parent 1: protocol ip handle 20 fw flowid 1:20
$tc filter add dev eth0 parent 1: protocol ip handle 30 fw flowid 1:30

# marking packets via iptables
$ipt -t mangle -I FORWARD -i eth1 -o eth0 -s 192.168.1.2 -j MARK --set-mark 20
$ipt -t mangle -I FORWARD -i eth1 -o eth0 -s 192.168.1.4 -j MARK --set-mark 30
$ipt -t mangle -I FORWARD -i eth1 -o eth0 -s 192.168.1.21 -j MARK --set-mark 10

Those settings result in packets from the mentioned sources (-s) being assigned to the classes defined above.