You could define a custom ErrorDocument for the 400 Errors like so:

ErrorDocument 400 /cgi-bin/handle400.cgi

and then have that cgi (or php or servlet or whatever) do the header rewriting and location redirecting.

EDIT: because of Jacek's answer I just tested above solution to confirm it works on Apache 2.2.

My Server Config:

ScriptAlias     /cgi-bin/ "/var/www/cgi-bin/"
ErrorDocument   400 /cgi-bin/handle400.pl

lukas$ cat /var/www/cgi-bin/handle400.pl

#!/usr/bin/perl
print "Content-type: text/html\n\n";
while (my ($key, $val) = each %ENV) {
        print "$key = $val<BR>\n";
}
exit 0;

Now when accessing the broken URL that would produce an error 400 Bad Request before, I now get the following (partial) output:

...
REDIRECT_REQUEST_METHOD = GET
REDIRECT_STATUS = 400
REMOTE_ADDR = xx.xx.xx.xx
REQUEST_URI = /%&%28%7B$%7Beval%28base64_decode%28$_SERVER%5BHTTP_EXECCODE%5D%29%29%7D%7D%7C.+%29&%/
GATEWAY_INTERFACE = CGI/1.1
SCRIPT_URL = /cgi-bin/handle400.pl
...

So you do get enough information to do a proper status code change and location redirect.

Quotation from Apache documentation:

Although most error messages can be overriden, there are certain circumstances where the internal messages are used regardless of the setting of ErrorDocument. In particular, if a malformed request is detected, normal request processing will be immediately halted and the internal error message returned. This is necessary to guard against security problems caused by bad requests.

So, if you want redirect error 400 you should uncomment ErrorDocument directive in httpd.conf Apache configuration file as follows:

# Some examples:
#ErrorDocument 500 http://foo.example.com/cgi-bin/tester
ErrorDocument 400 /cgi-bin/bad_request.pl
#ErrorDocument 401 /subscription_info.html
#ErrorDocument 403 "Sorry can't allow you access today" 

and restart Apache server.