I don't recall the name of the approach (or textbook), but my daughters have done some 'function machines' in 4th and 5th grade. They start by showing an image of a box with a conveyor belt bringing numbers in. Then different numbers leave. The students are asked to figure out what the box does to the incoming number to produce the new number.
In fourth grade they start with something /like/ this:
They generally start with simple addition or subtraction. Then they do multiplication or division. Then they will do a couple that are linear functions.
I consider this to be algebra for a 4th or 5th grader. I know we are, to a certain extent, in Lake Wobegon. But I can't imagine that our elementary teachers are the only ones out there that chose this textbook.
As I mentioned, I have been working on a project related to how we teach algebra. My goal is to present the material both differently and earlier than a traditional algebra 1 approach. For example, I don't see why we wait until algebra 2 or precalc to teach about functions. And I am always troubled by students who see algebra as a set of procedures rather than a language.