keynote video full screen
Now, the only time I used Keynote, was for an iPhone presentation for Steve Jobs... the client who created the slides and video basically asked for the same thing as you.
So here's what I would recommend...
First, make the document the size of the display you're going to view it on. Import the video into the slide. Once it's placed in there, scale it to the full width of the slide (Note: keep the shift key pressed down to scale proportionally). Now, depending on the aspect ratio of your video (i.e. 4:3, 16:9, etc...) you might have some blank space top and bottom. In this case, I just make the background black or white, depending on the design.