I must admit that I do not fully understand your last paragraph:
"I am not looking for a density plot (although those are often useful), I would want the same output as a simple plot call but much faster than millions of overplots if possible."
It is also unclear what type of plot (function) you are looking for.
Given that you have metric variables, you might find hexagon binned plots or sunnflower plots usefull. For further references, see
- Graphics of Large Datasets by Unwin/Theus/Hofmann
- Quick-R on "High Density Scatterplots"
- ggplot2's stat_hexbin
