TL;DR:
There seems to be a misconception between ALU as a box in high level discussion about computer structure and 'an' ALU as a concrete implementation of a logic to produce some calculative result.
Calculating devices have been in use for many years before von Neumann but he laid foundation for a terminology about the parts and an abstract description how binary implementation can be build from simple gates.
The Question:
How could early computers perform data operations before John von Neumann proposed the concept of ALU?
- By using an ALU. After all, von Neumann didn't propose something new but described (and published) what he learned/understood from the EDVAC project and their approach to build a computer.
Von Neumann's point about introducing an ALU (*1) in his 1945 paper "First Draft of a Report on the EDVAC" is to structure a subdivision of a computer system and name the parts. A step important to create a common wording to be used in following sections so he can elaborate on each. The subdivisions were:
- CA, a central arithmetic part,
- CC, a central control part,
- M, the memory,
- I, the input,
- O, the output and
- R, external recording (aka storage)
In addition CA and CC was to be combined into C, and together with M named the 'associative part' - what we may today call a processor.
The basic definition for an ALU was made to cover next to any 'thing' that can produce a result from an input:

(Taken from First Draft of a Report on the EDVAC p.1&2)
Later on he describes how binary numbers (not float) could be constructed and handled by using a simple logic block he called E-Element (*2). While he mentions that the E-Element is similar to what could be done with a triode, he does not go into circuit design but stays throughout the paper on an abstract, mathematical description.
Wikipedia vs. Complex History
[from Wikipedia]
Mathematician John von Neumann proposed the ALU concept in 1945 in a report on the foundations for a new computer called the EDVAC.
Being geared toward (and made by) a popular audience, Wikipedia doesn't always use the most careful wording. In this case the whole sentence and especially the use of 'proposed' might lead readers not firm with this topic into believing that von Neumann developed the ALU as a new idea which others implemented later on. It couldn't be further away from what really happened.
What Was There?
If that's so, how did computers earlier that von Neumann perform data operations without ALU? For example, how did they add numbers?
By using an adder? Which is a type of ALU.
As mentioned, von Neumann's idea about an ALU as distinct building block of a computer system isn't as much about concrete hardware (*3) but theoretical structure. Real world applications have existed way before.
This includes not only 'simple' adders in fixed or plug board configured machines but as well programmable computers. Most clearly to be seen by Konrad Zuse's Z1/Z3. Their designs were made in 1935, a full 10 years before von Neumann published his paper, while the Z3 was operational 4 years before.
The Zuse design features not only all of the building blocks von Neumann proposes - including operating from a central clock but also full fledged floating point on top.
Of course Zuse wasn't the only person to think about computers and in terms like von Neumann. After all, parts and
So What Did Happen?
It's the old story of Publish Or Perish - he who talks first and loudest will be cited and recognized most.
As mentioned in various sources von Neumann did not really create this out of nowhere, but published a summarised version of work developed by others he as been only in involved as part time consultant.
That rather short paper was distribute widely without any restrictions. As a result it was read and redistributed by many scholars. A perfect match for the needs of developers at the time. It's short and self contained nature without going too deep into hardware did of course help as well.
By nature any later description of a computer - all the way of today - is matching his structure, which of course means everyone citing his name to describe it in a single term. An almost classic example of the biblical Matthew Principle.
*1 - He didn't call it ALU either but called it the "Central Arithmetical part" or CA
*2 - Essentially a two input AND with one input inverted.
*3 - Were he goes later on into detail about how to create circuitry he opts for a bit serial design as that's not only the most simple to build, but as well the most basic, covering everything else. His argument was that parallel designs will only yield faster operation.
He sketches all necessary elements for his CA using examples of those E-Elements. Doings o he stays firmly on a descriptive theoretical side.