These devices already exist where the deaf person signs and the device produces a verbal translation. Search google for something similar.
>> Should I use a webcam?
>> -I considered this but with a computer the device will not be portable.
If portability is one of your requirements, then don't use a non-portable computer.
>> Should I use a cellphone?
>> -This makes it portable. But I don't know if the memory of a cellphone is enough to do complicated programs.
AFAIK, for an Android device, you should be able to access a fair bit of the device's memory if you use C/C++ and compile to native code. Otherwise the Java runtime will limit you to 16/24/48MB (depending on your OS version). Smart phones are pretty impressive performers... just make sure your algorithm is lean.
>> should I create a new device specifically for that?
>> -I don't have any idea on how to make a separate device.If this is a project that you must do, then this is not a suitable starting point.
I suggest that you develop the algorithm on a PC using a high level language, e.g. Matlab is very good for quick algorithm development, processing a recorded video (to give something consistent to test against) rather than interfacing the webcam. Once you have the algorithm working, you can port it to a mobile phone.