Your question is a bit confusing. DO you want something to happen when user selects contact in the lookup? (what if he selects one, then another one, then maybe selects 1st one again?)... I think some problematic scenarios sit in this area so maybe think again what you want to achieve... And if that's really it - Visualforce Case creation page (don't expect it to work when Case comes from outside like Web-to-Case, Email-to-Case, customer portal...)
If it has to happen on Case save... I don't think you can make cross-object workflows between Case and Contact and besides picklist updates in workflows are annoying (select previous/next value on picklist... wow, awesome, thx SF).
Trigger I'm afraid? Or some Javascript'y hack in the sidebar... or batch job that periodically checks new / changed Cases... Trigger sounds most accurate for this task.
P.S. It's not exactly "Parent" ;) If you'd have a master-detail relation between the two you could cheat by either making it a rollup summary or make a workflow on Contact "count of cases changed -> do something". Alas standard object can't be a "detail".
EDIT: Or maybe you're on the Case viewing page? Then you're one click away from editing the contact (hover over the link, balloon pops up, [edit])... If you really really need to do it from detail page - embed a VF page in the layout:
<apex:page standardController="Case" extension="myclass">
and in the Controller extension query for contact etc.