I briefly thought about starting a business like this a couple years ago. During this thought exercise I came to the conclusion that an embedded GPS would be essential to maintain security. Another idea would be making your social network your security system, by only allowing rentals to people within two degrees of separation on a social networking site.
GPS would be useless for a determined thief, be it by simply jamming the GPS/cell signal or a RF sniffer to locate the (cellphone/whatnot) transmitter in the car and destroy it. From what I see, your social network sanction would be the only feasible option.
There are not so many real expert thieves. That's why extended security measures do work: less experienced majority of thieves is caught outright, and more experienced minority of thieves is eventually caught due to unforeseen circumstances (unexpected witness, unexpected new security measure, etc.).
For example, GPS transmitter can stay silent until it gets "You are stolen" signal.
There could be more than one transmitter in a car. It may get activated only when on the move (and not in a garage) etc.