The (obvious?) non‑answer of sorts:
One can avoid the code‑bloat apparently necessary for one special case in non‑restoring division resorting to conditionally subtracting division instead.
See A faster drop-in replacement for libgcc s AVR division below the horizontal line.

The way to avoid a considerable number of additional instructions for divisor MSB set is to just prevent the process from ever returning to subtraction while processing dividend bits, taking a hit in expected and even in worst case cycle count.
AVR allows skipping the conditional jump implementing that in a suitable way. One more conditional fix‑up is needed before return. This overhead does not grow with operand size.

Below non‑restoring division disentangled from dividend&quotient shift by bytes. Worst case execution times are very similar; but due to the duplicated & bigger bit loop, non‑restoring takes about 59 instructions without movw where byte shift takes 39. The combined byte shifting non‑restoring division from the question code block can be modified the same way, raising worst case cycle count back above 500.

__udivmodsi4NonRestoring:       ; arg2, arg1 = divmod(arg1, arg2)
    clr     r_remHH
    clr     r_remHL
    mov_l   r_remL , r_remHL
    mov_h   r_remH , r_remHH
    ldi     r_cnt, 33
    rjmp    _udivmodsi4_ep

_udivmodsi4_pos:
    rol     r_remL              ;  1 shift dividend into remainder
    rol     r_remH              ;  2
    rol     r_remHL             ;  3
    rol     r_remHH             ;  4
    sub     r_remL, r_arg2L     ;  5 diminish remainder
    sbc     r_remH, r_arg2H     ;  6
    sbc     r_remHL, r_arg2HL   ;  7
    sbc     r_remHH, r_arg2HH   ;  8
    brcs    zero_bit            ; 10/9  remainder got < 0, was < divisor
    sec                         ; 10
_udivmodsi4_ep:
one_bit:
    rol     r_arg1L             ; 12/11 rotate 1 into quotient
    rol     r_arg1H
    rol     r_arg1HL
    rol     r_arg1HH
    dec     byteCnt
    brne    _udivmodsi4_pos     ; 18/17/16
    rjmp    bitsDone

_udivmodsi4_neg:
    rol     r_remL              ;  1 shift dividend into remainder
    rol     r_remH              ;  2
    rol     r_remHL             ;  3
    rol     r_remHH             ;  4
    add     r_remL, r_arg2L     ;  5 raise remainder
    adc     r_remH, r_arg2H     ;  6
    adc     r_remHL, r_arg2HL   ;  7
    adc     r_remHH, r_arg2HH   ;  8
    sbrs    r_arg2HH, 7         ; 10/9
    brcs    one_bit             ; 11/10 remainder restored to >= 0
zero_bit:
    lsl     r_arg1L             ; 11 shift 0 into quotient
    rol     r_arg1H
    rol     r_arg1HL
    rol     r_arg1HH
    dec     r_cnt
    brne    _udivmodsi4_neg     ; 17/16
    cp      r_remHH, r_arg2HH   ; if r_remHH smaller than r_arg2HH
    brcc    restore             ;     there was a carry
    inc     r_arg1L
    rjmp    bitsDone
restore:
    add     r_remL , r_arg2L    ; restore remainder
    adc     r_remH , r_arg2H
    adc     r_remHL, r_arg2HL
    adc     r_remHH, r_arg2HH
bitsDone:
    mov_l   r_arg2L,  r_arg1L   ; quotient
    mov_h   r_arg2H,  r_arg1H
    mov_l   r_arg2HL, r_arg1HL
    mov_h   r_arg2HH, r_arg1HH
    mov_l   r_arg1L , r_remL
    mov_h   r_arg1H , r_remH
    mov_l   r_arg1HL, r_remHL
    mov_h   r_arg1HH, r_remHH
    ret                         ; ~587 cycles worst case
sleep

A faster drop-in replacement for libgcc s AVR division
processing dividend bytes in a nested loop:

#define quotient    __tmp_reg__
#define dividend    __zero_reg__
#undef  r_cnt
#define r_cnt       r_arg1HH
__udivmodsi4B:
; no immediates for r0...r15 can be infuriating
;  with callee save for remaining r16,r17,r28,r29
;   ldi     r_cnt, 4        ; init loop counter - I wish
    mov     dividend, r_arg1HH
    ldi     r_cnt, 0xfb     ; init loop counters to 4 bytes of 8 bits
    clr r_remL    clr r_remH; clear remainder
    mov_l   r_remHL, r_remL
    mov_h   r_remHH, r_remH
byteLoop:
; failed: testing with a reduced core to avoid assuming unwarranted capabilities
;   ldi     quotient, 1     ; takes NBBY rol instructions to emerge as carry
    inc     r_cnt
__udivmodsi4_loopB:
; shift dividend into remainder
    lsl dividend    rol r_remL    rol r_remH    rol r_remHL    rol r_remHH
; compare remainder & divisor
    cp  r_remL ,r_arg2L     cpc r_remH ,r_arg2H
    cpc r_remHL,r_arg2HL    cpc r_remHH,r_arg2HH
    brcs    __udivmodsi4_epB; remainder <= divisor
; reduce remainder
    sub r_remL ,r_arg2L     sbc r_remH ,r_arg2H
    sbc r_remHL,r_arg2HL    sbc r_remHH,r_arg2HH
__udivmodsi4_epB:
    rol     quotient            ; (with CARRY)
    subi    r_cnt, 0x21
    brcc    __udivmodsi4_loopB  ; __zero_reg__ now restored (dividend == 0)
; com sets carry: control byteLoop by half-carry
    com     quotient            ; why not complement C?
    mov     dividend, r_arg1HL  ; shift by bytes. On reduced cores (no movw) one
    mov     r_arg1HL, r_arg1H   ;  additional (rjmp) instruction saves 2 cycles
    mov     r_arg1H, r_arg1L    ; shift on byteLoop top (skip on 1st iteration)
    mov     r_arg1L, quotient   ;  and adjust the quotient mov instructions
    brhc    byteLoop
; div/mod results to return registers, as for the ldiv() function
    mov_l   r_arg2L,  r_arg1L   ; quotient
    mov_h   r_arg2H,  r_arg1H
    mov_l   r_arg2HL, r_arg1HL
    mov_h   r_arg2HH, dividend  ; the last byte shift put the quotient MSB there

    mov_l   r_arg1L,  r_remL    ; remainder
    mov_h   r_arg1H,  r_remH
    mov_l   r_arg1HL, r_remHL
    mov_h   r_arg1HH, r_remHH
    ret
sleep

Shifting one byte of dividend instead of all four saves three cycles from each iteration of the bit-loop.
Alas, the compromise I chose to keep strictly with libgcc s size & "binary interface" expectations as well as with the "one binary fits all" philosophy led not only to an inane use of a loop control value:
it adds back one cycle to the bit loop, reducing worst-case speed-up from > 80 cycles to < 50.

Conceivably, speed-up will be smaller with a variant for "partial single" ints,
and take two instructions more than __udivmodpsi4.

Shifting dividend bytes and non‑restoring division being independent, this is the first stop on the way to fast, but large implementations, closely followed by the variant with sane loop control.
Non‑restoring division is an excellent candidate for the second stop,
combining both as in the question probably is the third.