You are right saying that without flushing rules, add_rewrite_rule() does not work, and the reason is that WordPress fetches rules from database, and add_rewrite_rule() does not add the rule to database.
However, is not possible to use admin_init and the reason is that admin_init is too late.
WordPress sometimes calls flush_rewrite_rules() on admin screens before that admin_init is fired (for example here), and to be sure the rule is added when WordPress calls flush_rewrite_rules() you need to use init (or maybe wp_loaded).
Something like this could work:
function addsomerule() {
if ( is_admin() ) add_rewrite_rule(some regex,some parse result);
}
add_action( 'init','addsomerule' );
It ensures that the rule is added only during admin requests.
However, the if statement that calls a function comes with a (little) cost in term of performance, and considering that the add_rewrite_rule is not very expensive (it only writes a value to a global array, and does not hit db), then probably it does not worth to add that condition.
Moreover, you don’t always have control on all the code your site uses. If some plugin calls flush_rewrite_rules() on frontend requests, then your rule is lost because added only on backend.
For all these reasons, add rewrite rules on init without any other check is probably the right thing to do: it avoids any issue and the little costs it adds on frontend requests is pretty much irrelevant and lost in the WordPress boot time.