I have some difficulty understanding how to go about with this problem:

I came up with several graphs, you can see them in the attached picture (they are up to ~g^4 order). I am not sure about the self-interaction diagrams, but I think they are considered in the connected graphs (they are not away from the external legs).

I am not sure whether here I'll have to also include the g^2 self-interacting graphs... without them I seem to be getting:
[itex]G \sim g^2 \Big( \frac{1}{s+m^2} + \frac{1}{t + m^2} + \frac{1}{u+m^2}\Big) \delta^4 ( k_1 + k_2 - k_3 - k_4)[/itex]
which looks OK compared to also including them.

By "self-interacting" you mean e.g. the first two in the second row? You are supposed to only consider connected graphs, so these two (and the very first one, and also some later ones) should not be there in the first place.

Also, I think there are more diagrams at 1-loop, e.g. more self energies and tadpoles...

At least in the conventions I am aware of, "connected" means that all external lines are connected to each other. A better definition might be something like "momentum conservation is not fulfilled by a subset of external momenta". These are the ones that actually give a contribution to the T-Matrix.