How fast do you need to fly so that heating makes anti-ice irrelevant?
The True Air Temperature (TAT) that the aircraft's skin will feel can be calculated from the Static Air Temperature (SAT) and the Mach number:
$$ \frac{\text{TAT}}{\text{SAT}} = 1 + \frac{\gamma - 1}{2} M^2 = 1 + \frac{1}{5} M^2 $$
(using $ \gamma = 1.4 $ for air). The SAT does not usually go below -56.5°C in the International Standard Atmosphere, which is the usual temperature in the lower stratosphere (where most supersonic aircraft fly).
At Mach numbers above $ \sim 1.24 $ the resulting TAT will be above 10°C, which is usually defined as the upper temperature, where icing conditions exist.
How does it depend on the part of the aircraft? Presumably the leading edge is the first part to warm up without anti-ice.
Yes, the leading edges would warm up most, but they are also the only part of the aircraft that could possibly accumulate ice. Aircraft that are certified for flight into known icing conditions typically have de-icing or anti-icing systems on the engine inlets, the propellers and the leading edges of the wings, vertical and horizontal stabilizer. But not all aircraft have these systems on all of these surfaces because they are not all affected equally. See e.g. these questions:
Are icing conditions different at typical supercruise altitudes? Is there meaningful water up there?
Humidity is usually quite low in the stratosphere, meaning icing isn't typically a problem here anyway:
The stratospheric air
masses sampled are dry, as expected, having mean
relative humidity over water of 12% and over ice of
23%, respectively. However, 2% of the stratospheric
data indicate ice supersaturation.
(A distribution law for relative humidity in the upper troposphere
and lower stratosphere derived from three years
of MOZAIC measurements)
Most weather phenomena only occur in the troposphere, which means you fly above the weather (although thunderstorm can push clouds to extreme altitudes).