They also list a 2GB one, but at the moment, no dice.
A 4GB shuffle would be borderline horrible, 1000 songs at random, heellll no, a 4GB iPod needs a screen, there's no way around it. Playing with that many songs needs some form of organisation and a way to view what's on there. I'd put more credence into the rumour of a 4GB flash based iPod mini now that Samsung has reportedly dropped the price of it's 4GB flash modules by 50% making them equal in price to the HDD's used in the current minis.
It would make for a wonderful device, ultra long battery life, you could make it thinner or keep it the same thickness and throw in a massive battery. Be good for the gym junkies too, they can show off a fully featured iPod now instead of tucking a shuffle somewhere out of the way.