I was thinking about this, and I think there are a number of ways to achieve this, and it would add another dimension to the show.
1. "Live" Audio interview - do the interview over the phone, and use some stills / video to show while that's on going. To record the audio, you could either record both ends seperately (ie have the interviewee record audio and then send the file) or record the phone audio. The former is trickier, but would probably have better sound. However, if you do the former, you could then re-record your end of the audio on video, so that you don't have to video yourself with a phone to your ear....
2. "Live" Video interview - similar to audio - you would need to get the other person to record the video from their end and send you the file to edit in.
3. Non-live video/audio - send a set of questions and get the interviewee to answer them either on audio or video, and then splice the questions in afterwards. This makes it harder to "ad-lib" during the interview, but means that you don't have to arrange a specific time to do the interview.
Hope this all makes sense - let me know if you have any questions about what I've said.

No that makes perfect sense,
No that makes perfect sense, in fact I ws thinking of inviting a few people on the show, to sit on the progbox couch :)