Is it possible to create a rewrite in WP dynamically such that no flushing is required?
For example, not storing the rewrite in the database but rather defined in my plugin code?
Yes it is possible, but there isn’t much point in that. The crudest way is to use a filter on the result of getting the ‘rewrite_rules’ option, and manipulating it by adding the entries you require directly to the array, and then you might need to filter those rules out when the option is updated.
The thing is that it is most likely a waste of time as as in real life rules do not change on every page load and therefore storing the aggregated rules in the options is an easy speed optimization.
OTOH if you need something to be extremely dynamic, then maybe rewrite rules are not the best way to go. You can write your own url parsing to be executed before the rewrite rules kick into action.