Do the QoS on your next hop router 

There is no next router. And QoS should be on the same machine.

or on the interface all your de-encapsulated VPN traffic flows over (ie. 'eth0') instead.

It is not a problem to find interface with de-encapsulated traffic. The problem is that tc rules should be written accoring to network device.
And it is really uncinvinient clone this rules which are differ only with destination IP.

For example look here. It's needed to create subclass for each destination IP.

#class
tc class add dev $DEV parent 1: classid 1:1 htb rate ${SPEED}kbit
#subclass
# high priority traffic (where we get money, http for example)
tc class add dev $DEV parent 1:1 classid 1:2 htb rate ${SPEED}kbit ceil ${SPEED}kbit prio 0
# low priority trafic - no adds - now money - low speed
tc class add dev $DEV parent 1:1 classid 1:3 htb rate ${SPEED}/2kbit ceil ${SPEED}kbit prio 1
#handle
tc qdisc add dev $DEV parent 1:2 handle 2: sfq perturb 10
tc qdisc add dev $DEV parent 1:3 handle 3: sfq perturb 10
#connect with
tc filter add dev $DEV parent 1:0 prio 0 protocol ip handle 2 fw flowid 1:1001
tc filter add dev $DEV parent 1:0 prio 0 protocol ip handle 3 fw flowid 1:1002