The statement "The action required MAY be carried out by the user  
agent without interaction with the user if and only if the method used  
in the second request is GET or HEAD." implies that it can be  
something other than GET or HEAD.
As to how to structure a POST Redirect (if it's practically possible  
as opposed to theoretically possible), I've no idea - haven't found  
any clues from my googling.
Sorry I couldn't be more of a help.
-- 
Pat
Augh, the horror and nightmares of this... I was working on an app that had
much the same problem, although in our case it was getting users to
authenticate themselves initially as they performed an action for the first
time that needed authentication.
The short answer to this is: you're boned.  You can't redirect to a non-GET
request (theoretical possibilities hinted at in RFCs notwithstanding --
kinda like trying to get a browser to make a non-GET/POST request without
JavaScript).
Now, workarounds. I came up with a few. They all sucked.
* Store the request method/parameters/etc in the session when doing the
  login thingy, and attempt to re-inject the request into the system when
  you're done.  The plumbing in Rails to make this work properly was just
  too hairy, and I gave up.
* Store the request method/parameters/etc in the session when doing the
  login thingy, and call out to an appropriate worker method when you're
  done logging in.  This seemed feasible at first (since there were a
  limited number of non-GET places people could hit and need to re-auth) but
  DRY and future expansion killed this one, and quite rightly so.
* Make sure that authentication checks for non-GET actions is done via JS
  first, and do the auth via AJAX.  This one almost kinda-sorta worked for
  us, although the HTTP/HTTPS shenanigans to make sure passwords weren't
  sent in the clear nearly killed me.  (I've got a blog post on that
  floating around somewhere).  Since the site I was working on was utterly
  useless without JavaScript, I could get away with it; if your site should
  be gracefully degradable, this is a non-starter.
* Re-architect the application to not need authentication on non-GET
  requests.  This is, depressingly enough, what we had to resort to in the
  end, since the JS solution turned out to suck in some way I don't recall
  now.  I suspect that this might not be such a winner for you, given the
  use case you've described, but you might have to resign yourself to the
  fact...
One insanely-irritating-but-nonetheless-possibly-feasible solution I've come
across recently is a JS-based pop-up that arrives out of nowhere when your
login has timed out, informing you that you've timed out and need to login
again.  You can then login in that popup, and then it goes away -- so you're
re-authenticated by the time you press that 'delete' button.  This falls
foul of popup blockers and needs JS as well, but in certain situations I can
imagine it might be the least-worst option.
Good luck. You'll need it.
- Matt
-- 
That's why I love VoIP. You don't get people phoning up to complain that the
network is down.
		-- Peter Corlett, in the Monastery
Generally speaking a POST is something nice to reconfirm, so perhaps in 
the case of a POST, the login screen should store the referrer URL 
rather than the intended/clicked URL.
That way, after login the user will go back to the screen they were 
initially at and they can click the POST button again.
- Andrew