We have had success using views, almost as it on the web. You're right, paging sucks and is not used. So, just don't page - count=-1 and dump it all out. That combined with gzip, smart categorization, jquery search, and predefined filters using show-single- category work well for us. It is super fast to load and scroll, even in IE. Gzip made it possible on the loading front. We get 85% compression most of the time.
We have very large databases too - 96Gb (thanks DAOS!) and 5+ million docs. Obviously you would want to limit the number of docs showing in a view to less than 2,500, but that is doable with categorization (twisty action).