When in Melbourne for Moodle Moot Au 2010 I noticed a row of shiny new blue bicycles next to Sandridge Bridge, at Southbank (just across the river from Fliders Street Station). This is an automated bicycle rental facility (called a "station"), part of the Melbourne Bike Share. The most useful feature of this system is that you do not have to return the bicycle to where you got it from, so you can rent from one station, pedal to another station and return the bicycle there. There is a very useful map showing where the bicycles are.
However, none of the bicycles from Sandridge Bridge seem to be out. I considered renting one, but then realised I did not have a helmet (which is required by law). The lack of helmets with the bicycles makes them of very limited use. The European cities I have seen similar schemes in (such as Berlin's Rent-a-Bike) do not require helmets. It may take some local ingenuity to get around the helmet problem to make the scheme a success in Australia.