This paper presents a new four-limbed robot, LEMUR IIb (Legged Excursion Mechanical Utility Rover), that can free-climb vertical rock surfaces. This robot was designed to have a number of capabilities in addition to climbing (e.g., assembly, inspection, maintenance, transport, intervention) and to be able to traverse a variety of other types of terrain (e.g., roads, talus, dirt, urban rubble). To maximize its flexibility in this regard, LEMUR IIb will need to exploit sophisticated control, planning, and sensing techniques in order to climb, rather than rely on specific hardware modifications. In particular, this paper describes a new algorithm for planning safe one-step climbing moves, which has already enabled LEMUR IIb to climb an indoor, near-vertical surface with small, arbitrarily distributed, natural features. To the authors' knowledge, this is the first experimental demonstration of a multi-use, multi-limbed robot climbing such terrain using only friction at contact points (i.e., free-climbing).