Let's say I contribute to a Roth IRA, and then my income ends up being higher than I expected for the year, above the IRS limits for Roth IRA contributions. I know I can recharacterize to a non-deductible Traditional IRA, but this isn't a very good deal relative to a taxable account, particularly if you already have deducted Traditional IRA money. Is it possible to somehow withdraw the money without any extra taxes or penalties? What if it has increased in value? Also, does it make a difference if I first contributed to a Traditional IRA, deductible because I did not have access to a 401(k), then recharacterized to a Roth IRA because I got access to a 401(k) partway through the year?
Yes, depending on the timing.
You generally can make a tax-free withdrawal of contributions if you do it before the due date for filing your tax return for the year in which you made them. This means that even if you are under age 59½, the 10% additional tax may not apply. These distributions are explained in Pub. 590-A.
I believe any growth is subject to the 10% penalty:
The 10% additional tax on distributions made before you reach age 59½ does not apply to these tax-free withdrawals of your contributions. However, the distribution of interest or other income must be reported on Form 5329 and, unless the distribution qualifies as an exception to the age 59½ rule, it will be subject to this tax.