"...especially since a large amount of programming is all
    about state and side effects."

Haskell provides lots of tools for reasoning about and managing side effects; it just doesn't (and, indeed, can't) allow them arbitrarily. In terms of interacting with the outside world—e.g. doing GUI work or interacting with a database—you usually have an effectful 'core' that manages side effects while a slew of pure helper functions operate on the data derived from those side effects. (This is good style in non-functional languages, as well, as it is a kind of separation of concerns.) Other functional languages are far less stringent about side effects, so both the ML family and Scheme allow state modification and side effects, although the functional style is preferred when possible.

In terms of writing algorithms, you'd be amazed at how little needs to be expressed in terms of manipulation of state. It feels natural to write stateful functions if you've spent large amounts of time programming in stateful languages, but that has more to do with your familiarity than a property inherent in the problem. If you were immersed in Scheme, you might say, "...a large amount of programming is about function definition and application", just like if you were immersed in Forth, you might say, "...a large amount of programming is about stack manipulation." You certainly could use e.g. Scheme as language for general-purpose programming, and I suspect the problems that would arise would not be problems with functional programming, but rather an unfortunate lack of modern libraries for things like Unicode handling.