One possible solution would be a 3D dimensional voronoi diagram.
Randomly generate a point cloud of the model's volume, with weight added toward the edges, then generate the voronoi pattern around the point cloud.
like:

we could then have sliders for total point density, and edge weighting.
Greater edge weight would mean larger gaps in the center, and smaller pockets toward the edge. zero edge weight would produce uniform pockets.
if you guys are good, you could have an 'infill volume' slider, and figure out the point density from there
I realize this could potentially add *minutes* to the slicing process, but the output would produce much stronger models with less filament, and potentially in less time.
If I'm prepping for a 12 hour print anyway, an extra 5 minutes isn't a problem.