Since a feat exists called Step-up that specifies that:
Whenever an adjacent foe attempts to take a 5-foot step away from you, you may also make a 5-foot step as an immediate action so long as you end up adjacent to the foe that triggered this ability. If you take this step, you cannot take a 5-foot step during your next turn. If you take an action to move during your next turn, subtract 5 feet from your total movement.
I would say that, no, you can not take your 5-foot step on another players turn, even if it is classified as "no action"
This entire situation is muddied a bit by the fact that the example for Attacks of Opportunity on 181 of the core rulebook states that a 5-foot step is a free action. Not that this affects that actual rules in the book and other tables, just that it is a bit odd.