I'd look into writing a Breeze DataServiceAdapter that inherits from the 'OData' adapter you're currently using as described here.
You'd override its executeQuery
method and do something appropriate when the URL gets too big.
The executeQuery
method for the stock 'OData' adapter is only 22 lines so it shouldn't be daunting.
You will note, however, that this adapter delegates to datajs. That means you'll have to figure out what facilities datajs offers for doing the $batch trick that you described. I don't know the answer to that myself. We'd all like to learn from you.