For passwords, sending a hash copy of the password would seem to be your best alternative. Notice that this avoids two of the problems you are considering: the hash of the password disguises the "secret" that you are transmitting, and the result of the hash can be expressed in a reasonable character set so that you don't have to worry about encode/decode. (Note: we haven't actually added any security by doing this).
I'm suspicious about using the url to communicate the credentials -- why not use the Authorization header? You wrote:
Any other operation in the API will be passed the user name and password for authorization purposes
Were you expecting to embed the credentials in every api call?
the operation is not idempotent
Then the operation is a POST. The most common answer that I've seen is to expose a "token collection" resource, and add a new token by posting the request to that resource. Principle of least surprise should maybe lean you this direction.
But you might re-examine your assumption that the operation isn't idempotent. Clearly, you don't want to have multiple tokens in your table -- but if the database rejects the command to inject a duplicate token, you've got the idempotent behavior that you need. You'll want to be consistent with HTTP put semantics, which means that you'll want the resource you are PUTting to be unique to the token.
Note that the token resource and the token entity are two different things. You can "create" the resource first, and then (if the client application follows that link) create the token. REST doesn't care - as long as the client is following links provided in the hypermedia, everything is good.
I'm struggling trying to force tokens into being a resource.
It shouldn't be too difficult, resources are cheap.
For instance, if your token is an analog of an HTTP cookie (one of the parts of the web that Fielding calls out as not being restful), then a flow of requests from the client might look like
POST /A
-- the server does its magic here, generating and storing a new token, which
-- it wants the client to reference in its subsequent requests
redirect: /B?token=54321
GET /B?token=54321
-- Now the server knows that this is a request for resource /B within the
-- context of the specific token. The representation of this resource
-- includes links to things that are also in the context of the token
returns: [representation including link /C?token=54321]
GET /C?token=54321
-- Subsequent calls stay in token=54321 space, until the server expires the
-- token and redirects the caller to some other representation of state.
Another alternative would be to separate out the reservation of the token identifier from the creation of the token
GET /A
-- here, the server generates a unique identifier for the token, without
-- doing any of the persistence work.
redirect: /B?token=54321
POST /B?token=54321
-- The client passes back to the server the id of the token, and the server
-- can choose to go create it and store it.
-- Notice: we aren't posting to the token resource, we are posting to
-- the resource identified by /B?token=12345; you get to decide what
-- that resource is. If the representations are suitable, and you can make
-- the operation idempotent now that the token identifier is fixed, you
-- might be able to use PUT rather than POST
returns: [representation including link /C?token=54321]
GET /C?token=54321
-- Subsequent calls stay in token=54321 space, until the server expires the
-- token and redirects the caller to some other representation of state.
If you wanted to be extra careful, you might implement resources that distinguish a reserved token from a persisted token.
GET /A
-- here, the server generates a unique identifier for the token, without
-- doing any of the persistence work. We're not making any changes to
-- the server state right now, so this is a reserved token.
redirect: /A?reservedToken=54321
GET /A?reservedToken=54321
-- this resource knows the token identifier, so it can now produce the
-- hypermedia control(s) that constrain the client to the reservedToken=54321 space.
-- We still haven't changed anything; this GET request is safe.
-- It's also potentially cacheable.
returns: [representation including link /B?reservedToken=54321]
POST /B?reservedToken=54321
-- The client passes back to the server the id of the token, and the server
-- can choose to go create it and store it.
-- Notice: we aren't posting to the token resource, we are posting to
-- the resource identified by /B?reservedToken=12345; you get to decide what
-- that resource is. If the representations are suitable, and you can make
-- the operation idempotent now that the token identifier is fixed, you
-- might be able to use PUT rather than POST.
redirect: /B?persistedToken=54321
GET /B?persistedToken=54321
-- Now this resource knows that the token has already been reserved, and
-- can generate additional hypermedia controls that constrain the
-- client to the persistedToken=54321 space. Once again, this GET
-- request is safe and cacheable.
returns: [representation including link /C?persistedToken=54321]
GET /C?persistedToken=54321
-- Subsequent calls stay in persistedToken=54321 space, until the server expires the
-- token and redirects the caller to some other representation of state.
The client is just choosing from the hypermedia controls provided by the server. So while this history would look like
GET /A
GET /A?reservedToken=54321
POST /B?reservedToken=54321
GET /B?persistedToken=54321
GET /C?persistedToken=54321
You can later decide that if these resource identifiers don't comply with your coding standards, or that they are to difficult to follow, or simply that you are bored with them, then you can change them all
GET /A
GET /W?reservedToken=54321
POST /X?reservedToken=54321
GET /Y?persistedToken=54321
GET /Z?persistedToken=54321
it looks almost impossible to force the stateful into stateless
-- It looks like you think REST implies lack of state. But nothing prevents you from saving the result of a REST call in a database, or storing cookies on the client's browser, or performing any other meaningful action involving some state. "Stateless" just means that each REST call can act independently of the others, which is always true.