AFAIK it is not possible to add new elements to the rendered HTML-page via the RichFaces' ajax-requests. I had a similar problem when displaying an output for a logfile which grows at runtime and tried to use the ajaxKeys-parameter of several RichFaces components - but without success. ajaxKeys is only applicable for rerendering existing rows.
Currently I rerender my whole logview-component.
probably most lightweight way to do that - just to play with oncomplete and data attributes. see the push demo(http://in.relation.to/Bloggers/GettingStartedWithRichFaces40Push). client side chat area updated via just jQuery on the client so it's not reRender anything:
ondataavailable adds one more line to the panel div instead of performing full panel rendering.
The only problem of that solution - elements added purelly on client side and have no representation in JSF components tree. So need to care about additional parameters which will identify them if need to perform some ajax actions on them later. And side problem - when you will render it completelly by ajax or perform page refresh all the elements added on the client side will disappear because of the same reason(facebook list also misses all lazy loaded stuff after refresh I believe.).