Suppose there is a language where, instead of statements, functions could only be defined in relation to other functions and operators such as partial application and composition. What would be the characteristics of such language? Could everything that is done with statements be done on this design? What would be the limitations? Are there languages like this?
It is Turing-complete, and has been used to write large business applications.
Although functions in Haskell are not supposed to have side effects, there are many that do, and act much like statements. (These are obviously necessary to do anything.) As an example, here is a Hello World example from Wikipedia:
module Main where main :: IO () main = putStrLn "Hello, World!"
It's not entirely clear what you are asking here. The concepts of "function" and "statement" are mutually incompatible: a function is a subroutine which returns a value, has no side-effect and is referentially transparent, whereas a statement doesn't have a value and thus must necessarily have a side-effect and thus cannot be referentially transparent.
So, a function can never be defined in terms of statements, only in terms of expressions.
So, yes, there are languages where functions cannot contain statements, namely all functional programming languages. These don't even have statements.
Haskell is a good example. (Note: Haskell actually does have statements. But not at the level of actual computation. For example, module import is a statement, or defining a type. However, those are compile time constructs, not runtime constructs, so, the idea of "returning a value" doesn't even make sense anyway.)
Note, there are also many languages which aren't functional languages that nonetheless don't have statements, e.g. Ruby, Io, Ioke, Seph, Smalltalk, Self, Newspeak, Scheme.
Or, are you talking about programming by combining functions? Then, again, yes, this does exist, and it is called "functional programming". In functional programming, you build programs by using functions as your main (and only!) building block and structuring tool, combining and manipulating them. There are even languages where functions are the only primitive the language provides. Again, Haskell, is an example. It does have things like numeric literals (e.g.
1), but you can interpret those as nullary functions.
Of course, the original manifestation of this idea is lambda calculus.
There are even languages where you don't even have functions, you only have combinators. Unlambda is such a language, which as its name suggests is one of the very few functional programming languages that is not based on lambda calculus. Instead, it is based on the SKI combinator calculus.
The SKI combinator calculus has only three primitives: the S combinator, the K combinator and the I combinator. (Actually, it turns out that the I combinator can be expressed as SKK, so it is not really primitive, you can get by with just S and K.) It doesn't have any sort of data: no booleans, no numbers, no nothing. (Just like lambda calculus.) However, unlike lambda calculus, it also doesn't have, well, lambdas (i.e. functions) nor variables. And yet, it is a Turing-complete model of computation which actually even precedes both Turing Machines and Lambda Calculus.