I would like to search ALL Subscribers on the basis of Subscriberkey and fetch a profile attribute 'ExternalId'
What AMPScript I can write for that? I don't think Lookup function works on All Subscribers.
Correct - All subscribers is a list. You need to use the API Ampscript functions detailed here.
Specifically, you are looking for InvokeRetrieve. There is example code for pull a subscriber from a list with a simpleFilterPart.