Japt, 19 13 bytes

No longer hampered by Japt not being able to get all substrings of a string (nor, too much, by my current levels of exhaustion!).

Outputs undefined if there's no solution.

ã fêQ á m¬æêQ

Try it

ã fêQ á m¬æêQ     :Implicit input of string
ã                 :Substrings
  f               :Filter by
   êQ             :  Is palindrome
      á           :Permutations
        m         :Map
         ¬        :  Join
          æ       :First element that
           êQ     :  Is palindrome

05AB1E, 13 12 bytes

ŒʒÂQ}œJʒÂQ}¤

Try it online!

-1 byte thanks to Magic Octopus Urn and Emigna.

Ruby, 131 123 120 bytes

->s{m=->t{t==t.reverse}
(1..z=s.size).flat_map{|l|(0..z-l).map{|i|s[i,l]}}.select(&m).permutation.map(&:join).detect &m}

Try it online!

A lambda accepting a string and returning a string. Returns nil when no solution exists.

-5 bytes: Replace select{|t|l[t]} with select(&l)

-3 bytes: Replace map{..}.flatten with flat_map{...}

-1 bytes: Loop over substring length and substring start, instead of over substring start and substring end

-2 bytes: Declare z at first use instead of beforehand

->s{
  l=->t{t==t.reverse}        # Lambda to test for palindromes
  (1..z=s.size).flat_map{|l| # For each substring length
    (0..z-l).map{|i|         # For each substring start index
      s[i,l]                 # Take the substring
    }
  }                          # flat_map flattens the list of lists of substrings
  .select(&l)                # Filter to include only palindromic substrings
  .permutation               # Take all orderings of substrings
  .map(&:join)               # Flatten each substring ordering into a string
  .detect &l                 # Find the first palindrome
}

Stax, 13 bytes

绬►Ö∞j∞:Æ╘τδ

Run test cases (It takes about 10 seconds on my current machine)

This is the corresponding ascii representation of the same program.

:e{cr=fw|Nc$cr=!

It's not quite pure brute-force, but it's just as small as the brute-force implementation I wrote. That one crashed my browser after about 10 minutes. Anyway, here's how it works.

:e                  Get all contiguous substrings
  {cr=f             Keep only those that are palindromes
       w            Run the rest of the program repeatedly while a truth value is produced.
        |N          Get the next permutation.
          c$        Copy and flatten the permutation.
            cr=!    Test if it's palindrome.  If not, repeat.
                    The last permutation produced will be implicitly printed.

J, 53 bytes

[:{:@(#~b"1)@(i.@!@#;@A.])@(#~(0<#*b=.]-:|.)&>)@,<\\.

Try it online!

Husk, 12 bytes

ḟS=↔mΣPfS=↔Q

Try it online!

Explanation

ḟS=↔mΣPfS=↔Q  Implicit input, a string.
           Q  List of substrings.
       f      Keep those
        S=↔   that are palindromic (equal to their reversal).
      P       Permutations of this list.
    mΣ        Flatten each.
ḟ             Find an element
 S=↔          that is palindromic.

JavaScript (ES6), 193 bytes

"Look Ma, no permutation built-in!" (So yes ... it's long ...)

Returns an empty array if there's no solution.

f=(s,a=[].concat(...[...s].map((_,i,a)=>a.map((_,j)=>s.slice(i,j+1)))).filter(P=s=>[...s].reverse().join``==s&&s),m=S=[])=>S=a.map((_,i)=>f(s,b=[...a],[...m,b.splice(i,1)]))>''?S:P(m.join``)||S

Demo

f=(s,a=[].concat(...[...s].map((_,i,a)=>a.map((_,j)=>s.slice(i,j+1)))).filter(P=s=>[...s].reverse().join``==s&&s),m=S=[])=>S=a.map((_,i)=>f(s,b=[...a],[...m,b.splice(i,1)]))>''?S:P(m.join``)||S

console.log(f('anaa'))
console.log(f('1213235'))
console.log(f('hjjkl'))
console.log(f('a'))

How?

Let's split the code into smaller parts.

We define P(), a function that returns s if s is a palindrome, or false otherwise.

P = s => [...s].reverse().join`` == s && s

We compute all substrings of the input string s. Using P(), we isolate the non-empty palindromes and store them in the array a.

a = [].concat(...[...s].map((_, i, a) => a.map((_, j) => s.slice(i, j + 1)))).filter(P)

The main recursive function f() takes a as input and compute all its permutations. It updates S whenever the permutation itself is a palindrome (once joined), and eventually returns the final value of S.

f = (                        // given:
  a,                         //   a[] = input array
  m = S = []                 //   m[] = current permutation of a[]
) =>                         //   and S initialized to []
  S = a.map((_, i) =>        // for each element at position i in a[]:
    f(                       //   do a recursive call with:
      b = [...a],            //     b[] = copy of a[] without the i-th element
      [...m, b.splice(i, 1)] //     the element extracted from a[] added to m[]
    )                        //   end of recursive call
  ) > '' ?                   // if a[] was not empty:
    S                        //   let S unchanged
  :                          // else:
    P(m.join``) || S         //   update S to m.join('') if it's a palindrome

Python 3, 167 bytes

lambda a:g(sum(k,[])for k in permutations(g(a[i:j+1]for i in range(len(a))for j in range(i,len(a)))))[0]
g=lambda k:[e for e in k if e==e[::-1]]
from itertools import*

Try it online!

-2 bytes thanks to Mr. Xcoder

Pyth, 13 bytes

h_I#sM.p_I#.:

Try it online!

-1 byte thanks to Mr. Xcoder

Coconut, 140 bytes

s->p(map(''.join,permutations(p(v for k in n(s)for v in n(k[::-1])))))[0]
from itertools import*
n=scan$((+))
p=list..filter$(x->x==x[::-1])

Try it online!

Jelly, 13 bytes

ŒḂÐf
ẆÇŒ!F€ÇḢ

Try it online!

Prints 0 in the invalid case.

Brachylog, 10 bytes

{s.↔}ᶠpc.↔

Try it online!

Fails (i.e. prints false.) if not possible.

Explanation

{   }ᶠ         Find all…
 s.              …substrings of the input…
  .↔             …which are their own reverse
      p        Take a permutation of this list of palindromes
       c.      The output is the concatenation of this permutation
        .↔     The output is its own reverse