One way is for Service A to establish a trust with Service B (ex. using SAML), and have the user at Service B authorize that usage. Service A and B agree on a unique key for that exchange (ex. private/public certs)
So how would the operator of service A prevent the service from stealing service A's private key with service B?
Of course, if Service B offers no such ability, then you'll need some sort of kludge like you suggested, but that doesn't make it right.
The kludge I suggested is a clunky way to describe the OAuth family of protocols, used by Twitter, Amazon MWS, and the like.
How much does one of those cost to buy and operate, especially if the rest of service A is small enough to run on shared hosting or a small VPS?