There were plenty of Android phones with less than 512MB memory in the beginning. Xperia X10 Mini had 256MB to take one I owned. And that was not because it was a complete freak, the full size X10 had 384MB.

I seem to remember a few phones with 128 meg, but looking at a few at GSM Arena they all have 192MB or more. I have my old Android dev phone (upgraded all the way to Cupcake!), and that has 192MB RAM. I wonder if that still starts.