One possible answer is that skew characters are not really the largest extension,
but a special-case of certain characters associated with any subset of boxes in the plane. For example, if this subset is the Rothe diagram of a permutation,
the character is a Stanley symmetric function.
It is an open problem, see
[Ricky Ini Liu, Specht modules and Schubert varieties for general diagrams. Massachusetts Institute of Technology. 2010] ,
to describe the Schur expansion of these (generalized Specht modules) combinatorially.
A quick (quick to implement) way to compute the Schur expansion of Stanley symmetric functions, is to sum over all reduced words of the given permutation, and then take the descent set of the reverse word.
The Schur expansion is then
$$
F_w(x) = \sum_{a \in RW(w)} s_{comp(DES(rev(a))}(x)
$$
where $rev(a)$ is the reverse of the reduced word,
$DES$ is the descent set, $comp$ is the classical map from subsets of $[n-1]$ to compositions, and a Schur polynomial indexed by a composition is computed via the first Jacob-Trudi identity.
The following code also works in Sage:
G = SymmetricGroup(6)
w = G.from_reduced_word(Permutation([2,4,6,1,5,3]).reduced_word())
f = w.stanley_symmetric_function()
s = SymmetricFunctions(QQ).schur()
s(f)
This example outputs:
s[3, 2, 1, 1] + s[3, 2, 2]