1) Has anyone ever made some kind of percentile graph of the big pools (like deepbit, etc.) ?
slush has this for his pool here
, I'm sure there are graphs for other pools as well.
2) Is there a max. time (or better max. number of operations) until a block will be found for sure (100%). Or could it happen that the time to mine one specific, nasty block could be millions of years?
There is no such max time. A block could theoretically take millions of years, the probability for that is positive though unbelievably tiny. The probability that a block will take at least N shares is roughly exp(-N/D) (where D is the difficulty).