Alternative block cipher design paradigms to SP-networks and Feistel-like ones?

Are ARX block ciphers considered there own class of block cipher separate from SPNs and Feistel-like ones?

Generally speaking, yes. ARX ciphers typically only use simple CPU instructions (Addition, Rotation, and Xor) and are typically designed to ensure constant time execution as well as to facilitate efficient SIMD implementations.

The s-boxes and split state that are so prevalent among SPN and Feistel Networks generally aren't present in ARX designs. I'm sure if you wanted you could come up with/find an example of an ARX Feistel network or build an SP network from ARX instructions, but I'm not sure what advantages it would offer.

Are there other schemes out there besides Feistel-like designs, SPNs, and ARX? Or is there really nothing new under the sun?

Typically, the ARX/SPN/Feistel part of the algorithm is used to create a "pseudorandom permutation", and the pseudorandom permutation is then used as part of a cipher construction to provide encryption.

The basic cipher construction is the iterated key or Even-Mansour construction. AES can be modeled like this, as an interleaved application of a key addition layer with the pseudorandom permutation.

A more recent cipher construction that can be built from an arbitrary pseudorandom permutation is the sponge construction. Technically the duplex construction is a stream cipher, rather then a block cipher. I think that this is actually a key point: The presumption that a block cipher is the best way to encrypt is not necessarily true.

Permutation based

Permutation based constructions are usually more versatile, and often times offer an all-in-one solution (authenticated encryption, hashing, MACs); While you could construct all of the above via a block cipher, it is much more straightforward from an implementation perspective to use a permutation based construction like the sponge construction.

Homomorphic Ciphers

There exist "linear" secret key ciphers, like this one from Fully Homomorphic Encryption Over The Integers. Typically these sorts of ciphers are designed to facilitate homomorphic encryption and/or to instantiate public key cryptosystems. They are often times built from number-theoretic perspectives, and clearly do not resemble any of the other cipher categories (and you would not use them for the same reasons).

The other main construction for a product cipher is the Lai–Massey scheme, which is considered a quasi-Feistel network. It is similar to a Feistel network in that it uses a (potentially non-invertible) F-function which has an input and output of half the block size, but it adds a full-width, invertible half-round function to protect against distinguishing attacks. It is secure in the Luby–Rackoff model.

Rather than acting on half of the block at a time and then swapping the two halves between rounds, the Lai–Massey scheme takes the difference between the two halves by subtracting them and feeds the result through the F-function, keyed with a round key. The output of the F-function is then added to both halves of the block. This construction would be vulnerable to a trivial distinguishing attack, so a simple half-round function that operates on the entire block is placed before each round. The half-round function may be keyed as well, but it can be omitted from the final round if it is unkeyed. In that case, the cipher is said to be an n.5 round cipher (such as IDEA, which is an 8.5 round cipher).

Consider an input block consisting of two halves of equal size, $(L_i, R_i)$. For round $i$, we compute $(L_{i+1}^\prime, R_{i+1}^\prime) = H(L_i^\prime + T_i, R_i^\prime + T_i)$ where $T_i = F_i(L_i^\prime - R_i^\prime)$ and $(L_0^\prime, R_0^\prime) = H(L_0, R_0)$ with $F_i$ being the F-function keyed with the round key for round $i$ and $H$ being the invertible half-round function. The final round omits applying $H$. Decryption is very similar, but with the addition replaced with subtraction (and vice versa), and $H$ replaced with its inverse, $H^{-1}$. If $H$ is keyed, then it is not omitted in the final round and, like $F$, is keyed with its own round key.

_{(Lai–Massey from Wikipedia, fixed to omit last half-round function.)}

Very few block ciphers use the Lai–Massey scheme. IDEA, designed by Xuejia Lai and James Massey, is the archetypal example. All of the others I am aware of are based on IDEA, including IDEA NXT, MESH, and the severely broken cipher Akelarre. None of those ciphers' published weaknesses are due to the Lai–Massey construction, but to weaknesses in their round functions.

If you count any block cipher, not just your typical product cipher, then the number of possible constructions goes up drastically. You start to see block ciphers with strange designs, such as the broken cipher KeeLoq which uses 528 rounds of an NLFSR and is often used for wireless car keys.

You are also able to design block ciphers from many other primitives, such as a public permutation using the Even–Mansour scheme, or from a length-doubling PRG (e.g. a stream cipher) by using the Goldreich–Goldwasser–Micali (GGM) construction to convert it into a PRF, which can be used as the F-function in a Feistel network in a block cipher (though there exist more efficient techniques).