Can I record a Skype call (audio and voice) using a Samsung Galaxy S3?
This probably is too late to be of help to the OP, but this question is valid and could be useful for others.

Found this: http://community.skype.com/t5/Video-INACTIVE/Record-video-calls-windows/m-p/3012#M44 but it pertains to windows and not the phone environment.

Unfortunately on android, Skype itself would have to have this feature for the best overall success.

Related topics with good answers: 


https://stackoverflow.com/questions/5382212/capture-video-of-androids-screen
https://stackoverflow.com/questions/3176555/android-capture-screen-of-phone-as-a-movie
Direct link: Droid@Screen


An on-phone solution to recording audio would have to simultaneously record incoming mic audio (from you) and outgoing speaker audio (from other). However, you could simply record the stream externally and use a movie/video editor to synchronize the video and audio streams.