You're right, there usually are too many subscribers in any ISP's network for their routers to be able to do full analysis and shaping on them. If they had routers with more juice, they would have even more subscribers! ;) That's where Deep Packet Inspection comes into play.
(I've never worked for any ISP, but I have been deep into DPI for years, during which I worked with all kinds of service providers, starting from small university campus networks, through small (~1000 subs) local ISPs, up to national cable providers and mobile operators with 1M+ subscribers. Just saying.)
As to the first two OSI layers, we usually sit inline somewhere in customer's network aggregation point, on any copper or fibre links. Throughput-wise we can usually handle about 500 Gbps per a fully juiced chassis. Works best if you put your DPI engine somewhere next to, or between two edge routers. This way we're seeing all traffic before it hits NAT or firewalls. From there on it's all about the logic in the engine and configuration.
Starting at the very basics, your public IP (or any external IP of your CPE) is the number one identifier in any small cable network. University campus networks, or ISPs who know your CPE MAC address, or deliver the CPE themselves, recognise your MAC address the moment you come on the network with a first DHCP request, and can from then provision this information to the engine so that you're recognised as a subscriber no matter what IP you receive. Easy stuff.
Things are usually a little bit trickier when you are a mobile network operator. In it, the DHCP leases are much shorter, change often, and come from a lot of different locations and directions in the network. In such case you usually connect to an external provisioning system, using RADIUS feed or DHCP snooper to react when a subscriber comes up online or disconnects. It may take up to a few seconds, but we usually recognise you within the first few kilobytes of your presence on the net. We can even slow you down to a lower throughput rate until we recognise you as a valid subscriber.
There are some more complex networks, for example with multiple VLANs with overlapping local IPs. Our engine can be configured to recognise subscribers by VLAN+IP pair, or by any other mean - L2TP tunnel ID, MPLS label + local IP, and so on.
This way we can really recognise every subscriber in real time. And since we have some good CPUs in the house and a lot of memory, we can do some great stuff like shaping of throughput, packets or connection rates per second.
[Before you shout at me for net neutrality, allow me to explain how there's good and bad shaping in networks. I agree that providers allowing some apps paid "fast lanes" is bad shaping. So is the manner in which VoIP applications are controlled and blocked often in countries east of Africa. However, tell an ISP with 1000 customers and 10 Gbps uplink he cannot shape, and you will run him down right out of business. Allow him to do fair sharing of the link between hosts on the network, or shape total BitTorrent in the network to some reasonable values, and all his customers could happily use their net to the max without any real problems. Give Skype and gaming a little higher priority, and never again hear complaints about lagging network. Seriously. We literally had customers calling us up after we've deployed shaping on their links, thanking us for improving their QoE without adding any throughput capabilities to their network.]
As to how shaping works, there's two ways of doing it. One is to modify and control TCP window sizes, so services like HTTP downloads don't send too many bytes per second. However, this only works for TCP traffic and is not very clean, since it's rewriting packets on the fly. A lot better solution is queueing packets and TXing them out in a controlled manner, or dropping them if the shaping queues get too close to the configured maximum.
What specifically happens inside a DPI engine is a secret of each company, so I can't talk too much about that. I can tell you that at its base we usually use our own implementations of known algorithms, like Blue (https://en.wikipedia.org/wiki/Blue_(queue_management_algorithm)). The way these work is they queue packets and start buffering them even before the maximum throughput is reached, to be able to react to any bursts of traffic on the link. It's more heuristic than just dropping excess traffic, so I recommend you give it a wider read if you're interested.
Finally, I've never seen two ISPs doing any real shaping on the link between their edge routers. I would expect the respected practice would be each one of them sticks to not exceeding the link speed towards their neighbour. Unless you know examples of such practice? I'd be curious to learn the details.