limiting per IP bandwidth for a full class A address range

We have PCs in class A subnet 10.0.0.0/8 which connect to Internet.
There is a linux box in between acting as a firewall. What we are
looking forward is to have a CIR (committed information rate) of
256kbps per IP, with any available bandwidth equally distributed among
active users (probaly we can use sfq for this!).

However, conventional way of having tc-filter for 2^24 IPs and having
2^24 classes looks to be tricky enough from management perspective.
What is the best way out for this?