Is it possible to register a sub-domain if you don't own the base domain?
For example, could I register NickLarsen.random.com if I don't own random.com?
No. This is not possible unless the owner of the domain allows it.
The Domain Name System distributes the responsibility of assigning domain names and mapping those names to IP addresses by designating authoritative name servers for each domain. Authoritative name servers are assigned to be responsible for their particular domains, and in turn can assign other authoritative name servers for their sub-domains.
The general you should believe is Oren's - however there is one exception to this rule.
If a domain is using http://freedns.afraid.org/ as their DNS provider and they've been lazy and not read the fine print, then anyone can create an A record as a subdomain to any domain listed on their site.
If you take a stroll around their site you can find a list of all the domains they have avaliable that you can create your own subdomain of.
Well, you could, technically speaking (configuring a DNS server for yourself, adding a zone file for the domain in question and creating an A or CNAME record for the subdomain in question), but it would work only for the people that use your DNS server to resolve domain names, so it really wouldn't work for that many people. And that's a good thing, because otherwise the Internet as we know it just wouldn't be, and there would be no real trust that you're actually on your bank's website or on a phisher's website.