Rule #1: Use example.com in your examples. All other addresses get auto-converted into active links. You don't want people to go to your page, you want them to see what you typed.
http://www.example.com/some%C3%ADtext
http://www.example.com/some%C3%A9text
http://www.example.com/some%F3text
even when trying myself with tildes I want it to redirect to the 404 page
http://www.example.com/s%EF%BF%BDme%EF%BF%BDtext
Ouch. I hope that last one wasn't meant to be your actual address, since it contains two "I can't deal with this" UTF-8 characters. You meet them most often when certain Latin-1 characters are reinterpreted as UTF-8 but they're in a forbidden range. Hence the need for example.com so the characters you typed can remain visible as Ã, é and ... ó? How on earth did you achieve that? (The first two came through in utf-8 encoding, the last in hexadecimal form instead of the expected %C3%B3.)
I'm missing something. If they're requesting pages that don't exist-- for whatever reason-- they should be landing on the 404 page anyway. Did you mean that you want to direct "vanilla" 404s and "special-character" 404s to different locations?
For instance, this rule won't work:
RewriteRule !^([_-a-zA-Z0-9\/]*)$ /not_found.php [L]
if gives an internal error (500)
Woo hoo, you have remembered Rule #2*, which is to explain
how it doesn't work. It may simply dislike the \/. Apache doesn't seem to like it when you escape characters that don't need to be escaped. (Some RegEx dialects don't care.) You are technically allowed to use ! in the Rule, but it has to be done with extreme caution. Save it for a preceding RewriteCond, where you can get away with more.
The second version, with your anchors,
RewriteRule ^([^_-a-zA-Z0-9\/]*)$ /not_found.php [L]
would only pick up requests consisting
entirely of non-ASCII characters. You are not likely to get many of those.
Do you have any pages that actually contain the % character? If not, and they've been encoded before they reach your .htaccess, it may be simplest just to say % (without anchors) meaning that something somewhere in the request has had to be encoded. Or %25 if other characters like / are also being encoded.
Error documents are generally static. What does the php do?
*
I made this up. But so far nobody has objected loudly.
