rules.js

{
  "rules": {
     "users": {
        "$user": {
           "username": {
               ".validate": "root.child('username_lookup/'+newData.val()).val() === auth.uid"
           },
           "email": {
               ".validate": "root.child('email_lookup').child(newData.replace('.', ',')).val() === auth.uid"
           }
        }
     },

     "email_lookup": {
        "$email": {
           // not readable, cannot get a list of emails!
           // can only write if this email is not already in the db
           ".write": "!data.exists()",
           // can only write my own uid into this index
           ".validate": "newData.val() === auth.uid"
        }
     },
     "username_lookup": {
        "$username": {
           // not readable, cannot get a list of usernames!
           // can only write if this username is not already in the db
           ".write": "!data.exists()",

           // can only write my own uid into this index
           ".validate": "newData.val() === auth.uid"
        }
     },
  }
}

usage.js

var fb = new Firebase(URL);

function escapeEmail(email) {
   return email.replace('.', ',');
}

function claimEmail(userId, email, next) {
   fb.child('email_lookup').child(escapeEmail(email)).set(userId, function(err) {
      if( err ) { throw new Error('email already taken'); }
      next();
   });
}

function claimUsername(userId, username, next) {
   fb.child('username_lookup').child(username).set(userId, function(err) {
      if( err ) { throw new Error('username already taken'); }
      next();
   });   
}

function createUser(userId, data) {
   claimEmail(userId, data.email, claimUsername.bind(null, userId, data.username, function() {
      fb.child('users').child(userId).set(data);
   );   
}