Everything that's shown in the video is technically possible within the game engine. In fact, if you have an NES Emulator and a copy of the game engine, you can download the set of inputs used in the video from Bisqwit's site and replay it back in-game yourself.
I don't really want to get into a discussion of whether or not using "frame advance" and "savestates" is "cheating", but what I said was that he wasn't "invincible." It's just that as far as the game knows, he never actually touched those things that could kill him. Usually, it involves moving in such a way or at such a speed that he's on one side of the enemy in one frame, and on the opposite side in the next frame, or by passing just outside of the enemy's "hitbox", even if the graphics representing the enemy or player are apparently touching.