Storyline or No Storyline

It's really up to you whether to have a story or not. I would say it depends on the game and what the goal of the game is. You could create a storyline for Snake if you really wanted to but a story is certainly not necessary in that context. If it's a complex game then a story would be good. If a story helps explain the motivation behind your game (Mario is searching for the princess) then a story would be good. In the end it is your decision.

If you didn't have any storyline at all, wouldn't it be hard to decide who and what the main character would be, who and what the enemies and obstacles would be, etc? For a sidescroller the choice is usually whether to have a game with minimal story vs. a game with a large amount of story. You can look at other sidescrollers you thought were great - how much story did they have?

I'd consider the list of gameplay elements you've built in the design. If you can play through, have fun, get immersed in the game design elements alone don't dilute it with a weak story. If the play through feels a bit squishy (pacing) or lacks in areas, use story to tie the elements or use story elements to add game design elements (like set pieces, chase scenes, etc).

Play test, play test, play test! You will know right away as you play through if bringing story to the art and code is required. Good question though. This is an important topic because so many games rely on weak tea story instead of getting really creative with game design elements. This is where you're game should shine. Fun first!

Take a look at mario and the Thing Thing games, neither really shoves a story in your face beyond the whole "mario running to save princess peach" and "Thing Thing some sort of genetic experiment and after breaking out of a lab is now being hunted down, shoot everything that moves as a result". The story is there to give a slight amount of meaning to everything but doesn't alter gameplay. Mario could well be searching off to find the legendary golden strap-on so he can have fun times with luigi, other than that being a very weird plot it wouldn't really alter the game much.

Personally, I almost invariably prefer story over no-story (most of the time what draws me to a game to begin with is its story, or at least its premise). But I think what matters the most is what you want out of the game. Remember: Most of the games amateur devs start don't actually go anywhere in the end. If you focus too much in the beginning on things that don't really interest you personally, you'll never be able to sustain your motivation throughout the duration of the project.

Just do like Nintendo did with most of their NES games and have a small storyline at the opening screen or when you complete a level, and make it completed in the manual(which you could just make a publicly available PDF).

The Legend of Zelda is a great example of this, but a better one is Super Mario Bros and the NES mario games. Look up the instruction booklets if you don't believe me.
http://www.mariomayhem.com/downloads/mario_instruction_booklets/index.php
There's also the NES game Metroid.
http://www.metroid-database.com/m1/manual.php
The Metroid series didn't really have an in-game storyline until Super Metroid. It didn't have the modern cutscenes with text that give games a continuing story until Metroid Fusion.

Financially, what matters most is the kind of content you personally can bang out quickly to make money. If writing is easy for you, by all means consider making a product where writing is a significant component of the content you deliver to the player. If writing is not so easy and rather much of a bogdown for you, then please feel free to skip it. When trying to make a game with an eye towards profit, as an indie, there are no "required checklists" of what you have to do in a game. For instance, Minecraft proved that you can make $80 million with 1 developer, ugly graphics, a less performing programming language, no tutorials, not so much gameplay, and no story.

If you don't care about money, then do whatever you want. If writing is hard, who cares? It's your excuse to become a better writer, or at least figure out if that sort of game development is for you.