plotting large number of points of different colours

I'd like to plot a large number of points (say 10**6 or 10**7) with
different colours. The colours will not naturally be parametrized by
a single float, but rather the rgb components will all vary
independently, so I don't think I can use a colormap. I've read the
tutorial, FAQ and skimmed the user's guide, and the only solution I've
found is to issue a separate

  plot([x], [y], '.', markeredgecolor=(r,g,b))

for each data point. But this appears to use huge amounts of memory
and be very slow.

I thought about using an image, but my points don't naturally fall on
a grid, and the plots will typically fill only 20 to 30% of the
canvas, so an image might not be best.

Various thoughts:

1) It would be nice if the above could be made fast, since it is
almost the first thing one might try, especially if one is generating
the points and the colours on the fly. (I say "almost" because it
wasn't obvious that I had to use markeredgecolor rather than
markercolor or just color.)

2) Alternatively, if I could specify an array of colors of the
same length as the xdata and ydata arrays, that would work for me,
but this doesn't seem to be supported currently.

If I ignore the colors, and plot my data using one (or just a few)
plot commands with marker '.', the speed is reasonable.

3) Scatter plots are close, but currently only allow a colormap
indexed by a single float. I'm also concerned about efficiency,
since every point seems to be plotted as a polygon, but I just
want small dots.

4) I could do like scatter does and use a collection of polygons.
I might try this, but am worried about plotting that many polygons.

Anything else I haven't thought of?