non-sequential, unique identifier, strategy question

(Please bare with me, I'm a new, passionate, confident and terrified programmer :D )

Background:
I'm pre-launch and 1 year into the development of my application.  My target is to be able to eventually handle millions of registered users with 5-10% of them concurrent.  Up to this point I've used auto-increment to assign unique identifiers to rows.  I am now considering switching to a non-sequential strategy.  Oh, I'm using the LAMP configuration.

My reasons for avoiding auto-increment:
1.  Complicates replication when scaling horizontally.  Risk of collision is significant (when running multiple masters).  Note: I've read the other entries in this forum that relate to ID generation and there have been some great suggestions -- including a strategy that uses auto-increment in a way that avoids this pitfall... That said, I'm still nervous about it.
2.  Potential bottleneck when retrieving/assigning IDs -- IDs assigned at the database.

My reasons for being nervous about non-sequential IDs:
1.  To guarantee uniqueness, the IDs are going to be much larger -- potentially affecting performance significantly

My New Strategy:
(I haven't started to implement this... I'm waiting for someone smarter than me to steer me in the right direction)
1.  Generate a guaranteed-unique ID by concatenating the user id (1-9 digits) and the UNIX timestamp(10 digits).
2.  Convert the resulting 11-19 digit number to base_36.  The resulting string will be alphanumeric and 6-10 characters long.  This is, of course, much shorter (at least with regard to characters) then the standard GUID hash.
3.  Pass the new identifier to a column in the database that is type CHAR() set to binary.

My Questions:
1.  Is this a valid strategy? Is my logic sound or flawed? Should I go back to being a graphic designer?
2.  What is the potential hit to performance?
3.  Is a 11-19 digit number (base 10) actually any larger (in terms of bytes) than its base-36 equivalent?

I appreciate your insights... and High Scalability for supplying this resource!