In my opinion, it should always use HTTP.
is REST web service implementation possible on any other protocol?
Yes, in theory it is possible because the REST(ful) style does not require HTTP.
According to Fielding, from his dissertation:
REST does not restrict communication to a particular protocol, but it does constrain the interface between components, and hence the scope of interaction and implementation assumptions that might otherwise be made between components. For example, the Web's primary transfer protocol is HTTP, but the architecture also includes seamless access to resources that originate on pre-existing network servers, including FTP, Gopher, and WAIS. Interaction with those services is restricted to the semantics of a REST connector
And I think the analogy to HTTP vs. other protocols on the web isn't a particularly good one - while seamless addressing is possible thanks to URLs, seamless access is only possible for clients that support those other protocols. For example, mainstream browsers can not interact with FTP servers beyond downloading.