I believe MapsWithMe (now Maps.me) was released about that time, but I personally didn't get an iOS device until 2013.

At that time I think I was using CityMaps2Go. Not sure if it still exists though.