While you can't modify the Definition Query that the layer was published with, you can still set a definition expression which gets appended to the default. We have an IOS app which works against 10.1 and 10.2 REST services which sets additional filters on the layer based on the user's inputs. The results will be only features which satisfy the published definition expression (which you can't retrieve in 10.2 REST) and the definition expression set on the feature layer in client code.
If the MapService allows layers to be added dynamically, then you might be able to create a new layer based off of one you want to change, set the definition expression, and add it to the map. I haven't tried this method yet.