Taking KEWR as an example, let us say that aircraft are taking off from 4L at N and landing on 4R. Can I be cleared to cross 4L at say V, behind the aircraft taking off on 4L, without interrupting the departure flow? Or will the runway need to be clear full-length to let me cross it?
You can cross behind the aircraft on departure roll. This type of operation is done heavily at ATL, on the middle complex during an east flow. Aircraft will depart runway 9L at M2, and arrivals from either of the south runway will cross behind them the whole time at M1, to get up to the gates.
At smaller airports with multiple runways, it is fairly common to get a runway crossing clearance behind an aircraft taking off (or landing). Sometimes the tower will ask you to cross "no delay" if there's another aircraft on short final so you don't get in the way of the arriving aircraft.