Since there are 40k to choose from, I imagine it's ok if there is a small lag until a record makes it into that 40k list?  If so, maybe Batch Apex could help?

Imagine something scheduled daily or several times daily.  It would run through all the records and build a JSON string within the batch apex run. Make sure to use Database.Stateful in the Batch Apex class.

In the finish method of the batch apex class, you'd have a monster JSON string.  Now you have to find a place to put it so you can pull it directly into a VF page.  Some ideas...

1) Have a Temp__c object with a bunch of long text fields on it.  Create a record there and fill in the long text fields. Get the ID of that to the VF page or setup the record so the VF page always knows how to find it.  Pull in the JSON.

Batch Apex sample code:

// Calculate the number of chunks to produce
String json = //the big JSON string from earlier in the batch class
Integer length = json.length();
Integer chunkSize = 32000; // long text fields are 32k
Integer chunks = Decimal.valueOf(length / chunksize).intValue() + 1;

if (chunks > 0) {

Temp__c t = new Temp__c();
t.Name = 'Auto Complete Data');

// Correct the chunks calc for a string of the exact chunk size
if (math.mod(length, chunksize) == 0){chunks = math.max(0, chunks - 1);}
				
if (chunks >= 1){ t.Long_Text_1__c = json.substring(chunkSize * 0, math.min(chunkSize * 1, length)); }

if (chunks >= 2){ t.Long_Text_2__c = json.substring(chunkSize * 1, math.min(chunkSize * 2, length)); }

if (chunks >= 3){ t.Long_Text_3__c = json.substring(chunkSize * 2, math.min(chunkSize * 3, length)); }

if (chunks >= 4){ t.Long_Text_4__c = json.substring(chunkSize * 3, math.min(chunkSize * 4, length)); }

if (chunks >= 5){ t.Long_Text_5__c = json.substring(chunkSize * 4, math.min(chunkSize * 5, length)); }

insert t;

}

2) Use an HTTP call and send it out to an external web server that creates a TXT file on it.  In your VF page, download the TXT file and turn the JSON into JavaScript objects

3) Somehow get it to be a Static Resource that you pull into your VF page and turn the JSON into JavaScript objects