I haven't done this but it doesn't sound too hard.
1) Write a js snippet that fires off a call to a a custom controller
action - let's call it check_user_attribute().
2) Wire this snippet up with the onblur event handler of form's fields.
3) In check_user_attribute, build user and check valid?, then check
errors on 'fieldname'. Update field as needed depending on outcome
Note that this is resource-intensive with all the remote calls and
running the full validation every time a user changes fields.