Here is a challenge that I like to try in Super Mario Bros. I haven't done it yet, but got to 8-3 on my best attempt. This is a true test of Mario skill. See if you can do it!

Rules:
1. Complete every stage of Super Mario Bros. from start to finish without dying once
2. Never pick up a mushroom
3. Therefore, never pick up a fireflower
4. Never pick up a star
5. Do not use any pipes (warp pipes or pipes within a stage) *except in Bowser's castle when you have to
6. Do not use any beanstalks.

Basically the idea is to make it as difficult as possible. Good luck!

EDIT: This is all one challenge. All six rules apply simultaneously.

I've done 1 and 4. I've never tried to beat the game without using a mushroom or flower before, however. That would be tough.

My goodness! I never use pipes or beanstalks, but no deaths? Then again, most of my deaths are usually from going after coins for extra lives.
I accept your challenge! (Don't expect much.)

7-2. Everything was going well until I inexplicably hit a fish. God dammit. 5-2 was a bitch as well with all those hammer brothers, but at least I survived that level. I feel depressed now.

@ Jeroen

Don't be depressed, you don't know how many times I've tried this, it really is hard. Yeah, getting by the first hammer brother in 5-2 can be tough.

You should add this to the challenge:

7. No walking on the top of levels (i.e. in World 1-2).

I usually use this rule in my playthroughs.

Without dying, I might (MIGHT) make it to like world 3. Bah.

Ugh, first try, was doing fine... until I got hammered on 5-2. And not in the good way.
Hammer brothers have always seemed ridiculously hard. Usually I get through them by having a mushroom and tons of lives by this point. I just jump randomly at them and hope for the best.

8. Have to play the harder version (with more buzzy beetles etc.)

9. Can't let the clock go below 100 seconds.

10. In water levels/sections can't walk along the bottom.

@Edwin: It was my first run, so I'm a lot more focused. I know for sure that next time I try to attempt a perfect run, I'll die in 4-3 or something because of a lack of concentration.

I've yet to beat Second Quest even with extra lives and powerups, so please no!
The other two stipulations don't seem like much. I never waste time running through, and walking along the bottom underwater is just slow (though it does help a bit in the last level, if I recall correctly).

@ Adam
regarding your #7...good point

@ CowLaunch
regarding your #8...I will try that once I do this challenge. #9...anyone good enough to do this challenge will probably be running through stages at near full speed so the time limit is really irrelevant. #10...I guess this would make it a little harder, as the bloopers can't get you, but the cheep cheeps still can.

I never find bloopers that difficult to avoid anyway. I prefer swimming just so it goes by faster. I'll try #8 if I ever beat the challenge with all the other stipulations.

When I'm going through the game as usual then I tend to run and jump past the hammer bros. and take my chances. If I undertook this challenge however, I think I would wait for the opprtunity to run under them because I only have one life and don't want to start all over again. If you wait long enough there's usually an opportunity to run under both hammer bros. and this could be quite time consuming in world 8 (you've got that far, so you'll want to take your time) That's where I think the time limit might come in.

I cant get past the 2nd level without dying,

11. Don't kill any enemies except, of course, for Bowser.

12. Don't collect any coins.

I don't know if that would necessarily be much harder or just annoying. Just throwing it out there as an idea. I'm still trying to beat the challenge of the original post (with the only addendum being no walking atop levels).

@Adam
Hmmm, sounds interesting, might not be actually feasible for some levels, I can't quite remember.

Now for the Lost Levels Challenge rules...

Lost Levels Challenge:

1. Beat the game.

All right, let's all get to work. We might have to ease up on the rules a bit, though. Suggestions welcome. Perhaps we could revise it to:

1. Beat a few levels of the game.

But yea, about my last SMB1 suggestions. I'm trying it right now, and there are road blocks early on. 1-2 is difficult to avoid killing enemies (though not impossible, it just makes me think later levels could be tougher than reasonably to be expected), and 1-3 has a couple coins I seem to get every time on accident toward the end. Probably do-able with divine patience though.

Lost Levels Challenge:

1. Refrain from destroying Wii console after playing.

2. After seeing game over screen for the 10th time, be pleasant to eveyone you meet for the rest of the day.

3. Avoid blaming the game or Nintendo.

As for Lost Levels. Try beating it 8 times. You have to before you can play worlds A, B, C, D. I am proud to say that I have done this. The good news is that you get unlimited continues, but the continue puts you at the start of whatever world you're on, not the stage you're on. 3 lives for every 4 stages, just be patient.