Yes I would have thought it is possible. It may however [badly] affect the workflow engine which I think has a limited number of workflow task executors. If one is held up waiting for your remote service then the other workflow requests would suffer. In general my rule of thumb is that workflow actions should be presented with all the data they need to work.
Being a Java programmer I'd write my workflow actions in Java and then I can call any remote interface such as web services or web scripts as appropriate. If I needed to worry about security or transaction handling then the APIs are available in Java.
I can imagine that others may try to script the calls. For example you could run an action that runs a script from your workflow.