É verdade que um aplicativo .NET 3.5 não será executado em uma instalação padrão do .NET 4.0, mas esse comportamento pode ser alterado com um arquivo de configuração simples. Normalmente, esse tipo de configuração seria feito por aplicativo, mas, dado o objetivo da sua pergunta, parece que você gostaria de um tipo de solução "configure uma vez e funcione em qualquer lugar". Você está com sorte porque o .NET tem essa capacidade.
Você não deve precisar de nada além do .NET 4.0 Full Profile e de um arquivo de configuração de máquina devidamente escrito. Depois de instalar o .NET 4.0 Full Profile, adicione um arquivo de configuração da máquina . Nesse arquivo de configuração de máquina, adicione uma seção supportedRuntime . Adicione uma seção supportedRuntime para cada versão do .NET que você deseja manipular pelo .NET 4.0 Runtime. (Adicionar suporte para .NET 1.0 é um pouco diferente.) Veja esta página para uma explicação completa de como segmentar uma versão do framework .NET .