Sites not using Typekit are most likely just using their own @font-face solution and hosting the fonts on their own server (which can also be a faster solution than loading in 3rd party font solutions).
Never use fonts and just hope a user might have it. It's not too hard to roll your own solution for serving up pretty fonts using @font-face. You will need to read up on it to learn the ins and outs, and what sort of goofy idiosyncrasies exits that you need to deal with.
I would recommend using the @font-face generator from fontsquirrel.com (http://www.fontsquirrel.com/fontface/generator). This helps you take a font you want to use and prepare it for the web, creating all the different font file types, as well as creating the css you need to use to embed the font for use.
When you use the font, be sure to use it as part of a font-family, so that you can plan what fonts to use as a fallback in case your @font-face declarations don't work out.
Understand that your font will be rendered differently between various browsers and operating systems. Sometimes using a css declaration like text-shadow (text-shadow: #FFF 0px 0px 1px;), and matching the text-shadow color to the background color the text is on, can help smooth out jaggies on the rendered font (works well for webkit browsers), YMMV. Definitely check out how your font looks in all the major browsers, as well as different OS platforms. For instance, I have found Windows XP to render some @font-face fonts much worse than say Windows 7.
Just know that things aren't quite perfect yet with @font-face, so think long and hard about using it in a production environment, and really test all platforms, browsers, etc to see how it looks. Understand how your choice to use a custom font might hurt readability for large blocks of small-sized text (like a blog post) because of rendering issues. Also, Remember to use custom fonts responsibly, you really shouldn't need more than 1 (2 max) custom fonts on a page. Some people get a little carried away.
Some free fonts you can use online. NOTE: Always check the font license to see if you are allowed to use it on your site. If you plan to make a profit on your site, always check to see if the font can be used commercially!:
Recommended reading (these should help you get in the head space of what you need to do, and what the @font-face landscape looks like right now):
I would question that statement. Specifying fonts a user "might have" is the entire basis of normal CSS font selection.
There's absolutely nothing wrong with specifying a somewhat unusual first choice. That's what fallbacks are for! For instance:
font-family: "Adobe Myriad Pro", Myriad, Georgia, Times, Times New Roman, serif;
Just make sure that you order them from most desirable to least desirable and it will display the best installed font.
I was thinking more along the lines of having some non standard font on your computer that would differ greatly from a common web-font, specifying that as the top choice in a font stack, and then designing your site using that font. Which I was thinking was essentially the goal of the OP.
I think your font stack example isn't quite as extreme as I was thinking in my head. Even still, your example has two sans-serif fonts that may/may not be on a users computer, with your fall back choices then being serifed fonts. Already, that font stack is setting your site up to present some very different designs to various visitors. That font stack would fare better if it was something like font-family: "Adobe Myriad Pro", Myriad, Lucida Sans Unicode, Lucida Grande, sans-serif;
If you are going to pick a non-standard font to use without font embedding, then your fallbacks should be web-safe fonts that are similar in design and in rendering size. Exotic Font Y at 16px can look much different from web-safe Font Z at 16px.
So, if a very small percentage of your users will have an exotic font installed that you want to use, and you aren't embedding that font for others to use, then you are setting yourself up for design/rendering problems for all of the people who have to use the fallback. It just ends up looking goofy and unprofessional, as well as being a bear to get to render nicely for both varying font styles in a "pixel perfect" design. Font stacks should be about trying to get the same experience across multiple platforms and browsers, not 30% get the best experience and 70% get a crummy degraded experience.
I definitely agree that you should be designing with the majority in mind. But if you set up good fallbacks then you can get 30% with fantastic type and 70% with quite decent type.
I don't tend to do "pixel perfect" design. I prefer designing in the browser, but can see how the traditional approach would make things difficult.
Fontspring offers @font-face licensing for professional fonts. I just used it because they have the very awesome Franklin Gothic family. It's also rather inexpensive($10-$20 avg perhaps) for unlimited domains. I prefer their model over something like TypeKit: Less restrictions and one-time-only payments.