React still eventually creates DOM nodes eventually, so I'm not sure what you mean.

How a custom element produces its DOM nodes are entirely up to it, and several approaches fit with a pure functional view of elements: 1) re-render and replace the entire component DOM, 2) Use a VDOM to patch the component DOM, 3) Use incremental-dom to update the component DOM, and yes 4) template systems like Polymer's can be easily used in a pure functional approach.

The key to being "stateless" isn't in abstracting away the DOM, it's in only using the inputs (attributes, properties, and children) to determine the DOM structure, and only allowing the host of an element to modify inputs so that the element behaves more like a function.

It's similar to mutable object that never modifies its own state, only has public state, and whose methods are pure. Method behavior is fully determined by state that the owner controls.

I think they meant that, if you build your stateless web component, you're likely going to have to either recreate DOM elements on every tick (if you're doing something like ng-repeat) or set a bunch of attributes and whatnot... unless you set up some caching mechanism

VirtualDOM is basically that caching mechanism