Do I have to make game with traditional platformer mechanics (walking and running) or are mechanics like teleporting and shooting allowed?

For sure, you can totally add non-traditional game mechanics! In fact, you bring up a great point- you could even work in a mechanic to fit the theme; like being able to swim when your not in water or something else thats out of place like that!