How long will an aircraft need to fly before it can land without dumping fuel?
Does it vary so much between aircraft types, distances,
  passenger/cargo weights and other conditions that it's not simply
  possible to say what is typical


This is pretty much the case. For example in a lot of smaller trainer aircraft you are more or less always in the CG range to make a successful landing. On the contrary in larger aircraft fuel burn schedules are extremely important to simply keeping the aircraft airborne. 

Dumping fuel is generally not idea from a strictly business standpoint you are basically throwing money out of the aircraft which no airline wants to do on purpose. 

What varies heavily between all flights is that at some point its up to humans, and humans make mistakes. Fuel loads may be calculated automatically but some guy still needs to usually shut the pump off at the right time, the pilots need to fly the plane as prescribed and the conditions need to be as expected. Any variable in this could create an issue for you.   

For example lets say you take off and get an unexpected tail wind of 100 Kts for the whole ride. Lets also say that you loaded up as much fuel as you could on account of you were flying to a smaller airfield and you were unsure they had enough fuel on hand to get you home. You knew you could bring enough to get there and back but you would be right at the limit of the load config. That 100Kt tail wind is going to save you a fair bit of fuel you intended on burning and due to unforeseen things you may now be over weight.

Now lets say you are flying short haul in a 737, you are doing a 30 min hop and its the end of the day. You have the the required fuel plus reserves so you are flying pretty light. A light passenger load and not much cargo to haul, you may be in range for the whole flight. 

Those are just two of a very long list of examples of different load configurations that can lead to always in range, or substantially out of range situations.