В общем, Вы правы, надо решать доступными способами.
После продолжительных поисков нашел скрипт мультироутинга: http://www.ssi.bg/~ja/tmp/mpath2.sh
Правила iptables я напишу, осталось решить с шейпером: каждому зарегистрированному адресу предоставлять канал 1 Мбит. Есть список IP-адресов, мы можем организовать цикл создания классов и очереди для каждого перечисленного в списке адреса, но,как описано здесь:
http://lartc.org/howto/lartc.adv-filter.hashing.html
это не слишком хорошая идея.
Есть еще вариант такой:
http://www.netfilter.org/projects/patch-o-matic/pom-external...
This option adds a `IPMARK' target, which allows you to mark
  a received packet basing on its IP address. This can replace even
  thousands of mangle/mark or tc entries with only one.

  This target is to be used inside the mangle table, in the PREROUTING,
  POSTROUTING or FORWARD hooks.

  IPMARK target options:
    --addr src/dst      Use source or destination IP address.
    --and-mask mask     Perform bitwise `and' on the IP address and this mask.
    --or-mask mask      Perform bitwise `or' on the IP address and this mask.

  The order of IP address bytes is reversed to meet "human order of bytes":
  192.168.0.1 is 0xc0a80001. At first the `and' operation is performed, then
  `or'.

  Examples:

  We create a queue for each user, the queue number is adequate
  to the IP address of the user, e.g.: all packets going to/from 192.168.5.2
  are directed to 1:0502 queue, 192.168.5.12 -> 1:050c etc.

  Earlier we had thousands of tc filter rules:
  tc filter add dev eth3 parent 1:0 prio 10 u32 match ip dst 192.168.5.2 flowid 1:502
  tc filter add dev eth3 parent 1:0 prio 10 u32 match ip dst 192.168.5.3 flowid 1:503
  ...
  or thousands of MARK rules (with tc fw classifier):
  iptables -t mangle -A POSTROUTING -o eth3 -d 192.168.5.2 -j MARK
    --set-mark 0x10502
  iptables -t mangle -A POSTROUTING -o eth3 -d 192.168.5.3 -j MARK
    --set-mark 0x10503
  ...

  Using IPMARK target we can replace all the mangle/mark rules with ONLY ONE:
  iptables -t mangle -A POSTROUTING -o eth3 -j IPMARK --addr=dst
    --and-mask=0xffff --or-mask=0x10000
  and all previous tc filter classifier rules with ONLY ONE:
  tc filter add dev eth3 parent 1:0 protocol ip fw

  On the routers with hundreds of users there should be significant load
  decrease (e.g. twice).

Но эта возможность доступна только при условии пересборки ядра, а мне такая роскошь не позволительна.
Возможно, Вам известны решения этой задачи, более элегантные, чем простое написание пары сотен правил шейпера?