It is possible, if you at the same time change both `{` and `}`.

The "simplest" (but not the fastest) solution is to use `l3regex`. However, it'll be hard to really use it, because it can't produce unbalanced input/output and therefore you can't use two steps to first replace `{` and in another step replace `}`.

Your issue is that everything you store in a macro must be balanced text. There are tricks to sort of get around that (see the `gtl` package, and no, it still stores balanced text, it just has an internal data structure that represents unbalanced text).

Since your use case can live with replacing both, you can get that outside of `str` as well, since as long as the result is balanced we can replace balanced `{}` with something else. Proof of concept using my `etl` package:

```
\documentclass{article}

\usepackage{etl}

\ExplSyntaxOn
\etl_new_if_in:Nnn \__my_if_contains_opening_brace_macro:n \{ { TF }
\cs_new:Npn \my_replace_group_delimiters:nnn #1#2#3
  {
    \__my_if_contains_opening_brace_macro:nTF {#2}
      {
        \exp_args:Nee \__my_replace_group_delimiters_aux:nnn
          {
            \__my_replace_group_delimiters_prepare:Nnn
              \{
              { { \if_false: } \fi: }
              {#2}
          }
          {
            \__my_replace_group_delimiters_prepare:Nnn
              \}
              { \if_false: { \fi: } }
              {#3}
          }
          {#1}
      }
      {
        \__my_replace_group_delimiters_aux:nnn
          { \exp_not:n {#2} }
          { \exp_not:n {#3} }
          {#1}
      }
  }
\cs_new:Npn \__my_replace_group_delimiters_prepare:Nnn #1#2
  {
    \etl_act:nnnnn
      { \__my_replace_group_delimiters_prepare_aux:NnnN #1 {#2} }
      { \use_i:nn { ~ } }
      { \__my_shipout_exp_not_group:nn }
      {}
  }
\cs_new:Npn \__my_shipout_exp_not_group:nn #1#2
  { { \exp_not:n { \exp_not:n {#2} } } }
\cs_new:Npn \__my_replace_group_delimiters_prepare_aux:NnnN #1#2#3#4
  {
    \etl_token_if_eq:NNTF #1#4
      { \exp_not:n {#2} }
      { \exp_not:n { \exp_not:N #4 } }
  }
\cs_new:Npn \__my_replace_group_delimiters_aux:nnn #1#2
  {
    \etl_act:nnnnn
      { \use_i:nn \exp_not:N }
      { \use_i:nn { ~ } }
      { \__my_replace_group_delimiters_aux:nnnn {#1} {#2} }
      {}
  }
\cs_new:Npn \__my_replace_group_delimiters_aux:nnnn #1#2#3#4
  {
    #1
    \__my_replace_group_delimiters_aux:nnn {#1} {#2} {#4}
    #2
  }
\cs_generate_variant:Nn \my_replace_group_delimiters:nnn { V }
\cs_new_protected:Npn \my_replace_group_delimiters:Nnn #1#2#3
  { \tl_set:Ne #1 { \my_replace_group_delimiters:Vnn #1 {#2} {#3} } }
\ExplSyntaxOff

\begin{document}
\ExplSyntaxOn
\tl_set:Nn \l_tmpa_tl { { abcd } }
\my_replace_group_delimiters:Nnn \l_tmpa_tl { pqr~ } { ~xyz }
\l_tmpa_tl
\par

\cs_generate_variant:Nn \str_replace_all:Nnn { NV }
\str_set:Nn \l_tmpa_str { { abcd } }
\str_replace_all:NVn \l_tmpa_str { \c_left_brace_str }  { pqr~ }
\str_replace_all:NVn \l_tmpa_str { \c_right_brace_str } { ~xyz }
\str_use:N \l_tmpa_str
\ExplSyntaxOff
\end{document}
```

You get the following syntax:

- Every `{` in `#1` is replaced by `#2`, every `}` in `#1` is replaced by `#3`.
- In `#2` every `\{` gets treated as an unbalanced `{`, and in `#3` every `\}` gets treated as an unbalanced `}` (you can still use balanced `{}` in both of these arguments and they get passed on as they are).
- The result has to be balanced (so for every `\{` in `#2` there must be a `\}` in `#3`, and they must not be used inside `{}`, well they can, but are not altered there)

So `\my_replace_group_delimiters:nnn { a { b } c } { \{~ } { ~\} }` results in `a {~ b ~} c`, and `\my_replace_group_delimiters:nnn { a { b } c } { \{\{ } { \}\} }` results in `a {{ b }} c`.