If it's a browser 301 for the customer's convenience
Or you could just serve the browser a true 404 http header with a custom page to help the use navigate the site. I have served the browser a carbon-copy of the home page on some sites, but as a different url. That's probably a better bet than playing with user-agent delivery whcih might be interpereted as deceptive cloaking in some situations.
I suppose google could get paranoid about different returns but I don't see why it should. The web site is there for the punter's benefit, not google's.
There are a lot of reasons for legitimately "cloaking" certain content to stop google etc seeing it. The important thing is not to give them "spam" content that the punter doesn't see. Google should view what they are given and make decisions on that.
My personal view is that google are calling far too many scares and people are playing their game - we have to or lose trade. It's time they settled down a bit. :)