should always return a pointer to class in interface design?

Your observations are correct, there is no easy way to do what you want to do. In C++ you can't return a Car by value because (among other things) the caller needs to allocate space for it.

Java isn't fundamentally different, it is just that its syntax can't express what you want to express - all types (except the primitive types) have an implicit '*' attached to them. And it has garbage collection, so you don't need to worry about memory management.

In Java, "returning and object" is actually semantically equivalent to returning a pointer to the object in C++, you are trying to return an object by value, which makes a copy of it. You can't make a copy of an abstract object.

So, while C++ may be more verbose, it supports different semantics for passing parameters and returning values, which Java doesn't support (return by value, pass by reference).

With that said, you should return by smart pointer, which does memory management for you. Others have pointed out auto_ptr with ownership transfer semantics, but you can also use boost::shared_ptr, in case you use custom memory allocation internally (e.g. a pool), shared_ptr's custom deleter feature will help you hide deallocation details from the user of the interface. It can also be used in STL containers (unlike auto_ptr).

class Car
{
public:
    typedef boost::shared_ptr<Car> Ptr;
    virtual int price() = 0 ;
    virtual string brand() = 0 ;
};

class Interface
{
public:
    virtual Car::Ptr giveMeACar() = 0 ;
    virtual vector<Car::Ptr> listMeAllTheCars() = 0 ;
}