I know I want an initative roll type system for who goes first but past that I am not sure what kind of mechanics would promote creative problem solving.
The easy way is to simply make it one of the most effective ways to deal with things in combat.
The oldest example would be Tunnels and Trolls - each round you can either contribute directly to combat attack & defense, OR you can do a "Saving Throw" (T&T used Saving Throw to mean any possible attribute/skill check). If you did a Saving Throw, the GM would decide what possible outcomes would make sense - "I throw a bag over the monster's head so it can't see!" "Ok, that's a Dex Saving Throw level 3, and if you succeed it isn't able to do any damage this round."
Sorcerer had the GM give players 1-3 bonus dice for tactically smart, dramatically entertaining combat choices.
There's three things necessary to make this work in your game design:
It has to have mechanical impact. That can be bonus dice/better damage/conditions, but it has to be a better than basic powers/attacks.
The players have to know that this is viable option and a good choice.
The GM has to be taught how to judge/apply these things, and how to frame scenes/encounters with plenty of stuff to creatively solve things.
Very old school D&D somewhat dealt with creative solutions, mostly through use of objects + magic, but it primarily was a negative reinforcement cycle - if you didn't cheap your way through/around an encounter, it became very easy to get killed. Positive reinforcement works better and to what level it helps depends on how your system is built.