The easy way to do it is to cook the rice first (in a saucepan with a lid on it), using just enough water/stock so that all of the water has evaporated just as the rice is ready. Then throw the rice into a frying pan with a little olive oil and add the other ingredients.
Of course, using the right type of rice to start with helps a lot. If you can afford it (and find it in the shops), use Bomba rice. Otherwise seek out a good short grain rice, such as Senia, Bahia or Calasparra. If you use a long-grain rice (of the type that you'd use for a curry or risotto) you've no chance of getting a good result with paella.