The Minneapolis Issues List has an interesting thread going about shared bike programs in Paris and Copenhagen.
Basically, they have an hour-car style model using a bus-pass type card to gain access and pay for the bikes at a rate of approx. $1.38/day.
The Copenhagen plan mentioned sounds interesting too: charge a deposit for use, but give it back when you (or someone else) returns the bike.
Both seem to solve the issue with having purely free bikes like St. Paul tried around 15 years ago near Macalester. With no liability, the bikes were trashed and/or disappeared, making the program a failure. It looks like the newer approaches have more potential.