Short time-scale coulomb counting
It is not difficult to integrate current. If you're willing to roll your own you'll have complete control over the specs.

As you probably know, a capacitor has the relationships Q = CV and \$Q = \int i \cdot dt\$ .

One way I see off the top of my head to do this is to create a current mirror to charge a cap. Reading off the voltage of the cap is all that is needed. You can get caps as accurate as you need and there are many accurate current mirror configurations.

With such a method you can really get any amount of complexity that you need. You could have multiple resolutions(multiple mirrors and caps of different sizes). You can use op amps to improve the resolution and create a simple reset. 

Of course it's not as simple as using a chip but as you have already stated, you can't find any chips that suit your needs.

It may be possible use current sensing(even proximity) but I'm not sure the accuracy you will get. For example, if your load is fairly low you could stick a 1ohm resistor in series. The voltage across the resistor is then equal to the current. Integrate this(say, using an op amp) and you have the charge. The efficiency here would be much larger, almost near unity while the current mirror method will be slightly less than 50%.